AOT produce the same code several times

[jensjoha]

Say I have this file

import 'dart:io';
import 'dart:typed_data';

void main() {
  File f = new File.fromUri(Platform.script);
  Uint8List bytes = f.readAsBytesSync();
  Reproduction reproduction = new Reproduction(bytes);
  reproduction.reproduce();
}

class Reproduction {
  final Uint8List bytes;
  final int bytesLengthMinusOne;
  int byteOffset = 0;
  Reproduction(this.bytes) : bytesLengthMinusOne = bytes.length - 1;

  @pragma('vm:unsafe:no-bounds-checks')
  int advance() {
    ++byteOffset;
    if (byteOffset > bytesLengthMinusOne) return -1;
    return bytes[byteOffset];
  }

  @pragma('vm:unsafe:no-bounds-checks')
  @pragma("vm:never-inline")
  int reproduce() {
    int localByteOffset = byteOffset;
    while (localByteOffset + 10 < bytesLengthMinusOne) {
      // Here we can access bytes without checks
      int next = bytes[++localByteOffset];
      if (tableLookup(next) &&
          tableLookup(next = bytes[++localByteOffset]) &&
          tableLookup(next = bytes[++localByteOffset]) &&
          tableLookup(next = bytes[++localByteOffset]) &&
          tableLookup(next = bytes[++localByteOffset]) &&
          tableLookup(next = bytes[++localByteOffset]) &&
          tableLookup(next = bytes[++localByteOffset]) &&
          tableLookup(next = bytes[++localByteOffset]) &&
          tableLookup(next = bytes[++localByteOffset]) &&
          tableLookup(next = bytes[++localByteOffset])) {
        continue;
      }
      // If we got here the latest value into next returned false.
      byteOffset = localByteOffset;
      return next;
    }

    // Less than 10 bytes left in stream.
    while (true) {
      int next = advance();
      if (next == -1 || !tableLookup(next)) {
        return next;
      }
    }
  }
}

@pragma("vm:prefer-inline")
bool tableLookup(int next) {
  const List<bool> tabel = [
    // format hack.
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, true, false, false, false,
    false, false, false, false, false, false, false, false,
    true, true, true, true, true, true, true, true,
    true, true, false, false, false, false, false, false,
    false, true, true, true, true, true, true, true,
    true, true, true, true, true, true, true, true,
    true, true, true, true, true, true, true, true,
    true, true, true, false, false, false, false, true,
    false, true, true, true, true, true, true, true,
    true, true, true, true, true, true, true, true,
    true, true, true, true, true, true, true, true,
    true, true, true, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    false, false, false, false, false, false, false, false,
    // format hack.
  ];
  return tabel[next];
}

The aot compile produce code like this:

148: B23[target]:200
150:     ParallelMove r9 <- rax, rax <- rbx goto:202 B14
152: B22[target]:196
154:     ParallelMove r9 <- rax, rax <- rbx goto:198 B14
156: B21[target]:192
158:     ParallelMove r9 <- rax, rax <- rbx goto:194 B14
160: B20[target]:188
162:     ParallelMove r9 <- rax, rax <- rbx goto:190 B14
164: B19[target]:184
166:     ParallelMove r9 <- rax, rax <- rbx goto:186 B14
168: B18[target]:180
170:     ParallelMove r9 <- rax, rax <- rbx goto:182 B14

or disassembled:

        ;; B23
        ;; ParallelMove r9 <- rax, rax <- rbx goto:202 B14
0x7f884cbad868    4989c1                 movq r9,rax
0x7f884cbad86b    4889d8                 movq rax,rbx
0x7f884cbad86e    e953000000             jmp 0x00007f884cbad8c6
        ;; B22
        ;; ParallelMove r9 <- rax, rax <- rbx goto:198 B14
0x7f884cbad873    4989c1                 movq r9,rax
0x7f884cbad876    4889d8                 movq rax,rbx
0x7f884cbad879    e948000000             jmp 0x00007f884cbad8c6
        ;; B21
        ;; ParallelMove r9 <- rax, rax <- rbx goto:194 B14
0x7f884cbad87e    4989c1                 movq r9,rax
0x7f884cbad881    4889d8                 movq rax,rbx
0x7f884cbad884    e93d000000             jmp 0x00007f884cbad8c6
        ;; B20
        ;; ParallelMove r9 <- rax, rax <- rbx goto:190 B14
0x7f884cbad889    4989c1                 movq r9,rax
0x7f884cbad88c    4889d8                 movq rax,rbx
0x7f884cbad88f    e932000000             jmp 0x00007f884cbad8c6
        ;; B19
        ;; ParallelMove r9 <- rax, rax <- rbx goto:186 B14
0x7f884cbad894    4989c1                 movq r9,rax
0x7f884cbad897    4889d8                 movq rax,rbx
0x7f884cbad89a    e927000000             jmp 0x00007f884cbad8c6
        ;; B18
        ;; ParallelMove r9 <- rax, rax <- rbx goto:182 B14
0x7f884cbad89f    4989c1                 movq r9,rax
0x7f884cbad8a2    4889d8                 movq rax,rbx
0x7f884cbad8a5    e91c000000             jmp 0x00007f884cbad8c6

i.e. the same code copied 6 times which seems odd (to me).

/cc @mraleph

[dart-github-bot]

Summary: AOT compilation generates redundant code. The ParallelMove instruction sequence is repeated multiple times, suggesting an optimization issue.

[a-siva]

//cc @alexmarkov

[alexmarkov]

Larger range of relevant code:

        ;; B24
        ;; ParallelMove r9 <- r9, rax <- rbx goto:214 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c150    4889d8                 movq rax,rbx
0x7fd20438c153    e95e000000             jmp 0x00007fd20438c1b6
        ;; B23
        ;; ParallelMove r9 <- rax, rax <- rbx goto:210 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c158    4989c1                 movq r9,rax
0x7fd20438c15b    4889d8                 movq rax,rbx
0x7fd20438c15e    e953000000             jmp 0x00007fd20438c1b6
        ;; B22
        ;; ParallelMove r9 <- rax, rax <- rbx goto:206 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c163    4989c1                 movq r9,rax
0x7fd20438c166    4889d8                 movq rax,rbx
0x7fd20438c169    e948000000             jmp 0x00007fd20438c1b6
        ;; B21
        ;; ParallelMove r9 <- rax, rax <- rbx goto:202 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c16e    4989c1                 movq r9,rax
0x7fd20438c171    4889d8                 movq rax,rbx
0x7fd20438c174    e93d000000             jmp 0x00007fd20438c1b6
        ;; B20
        ;; ParallelMove r9 <- rax, rax <- rbx goto:198 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c179    4989c1                 movq r9,rax
0x7fd20438c17c    4889d8                 movq rax,rbx
0x7fd20438c17f    e932000000             jmp 0x00007fd20438c1b6
        ;; B19
        ;; ParallelMove r9 <- rax, rax <- rbx goto:194 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c184    4989c1                 movq r9,rax
0x7fd20438c187    4889d8                 movq rax,rbx
0x7fd20438c18a    e927000000             jmp 0x00007fd20438c1b6
        ;; B18
        ;; ParallelMove r9 <- rax, rax <- rbx goto:190 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c18f    4989c1                 movq r9,rax
0x7fd20438c192    4889d8                 movq rax,rbx
0x7fd20438c195    e91c000000             jmp 0x00007fd20438c1b6
        ;; B17
        ;; ParallelMove r9 <- rax, rax <- r13 goto:186 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c19a    4989c1                 movq r9,rax
0x7fd20438c19d    4c89e8                 movq rax,r13
0x7fd20438c1a0    e911000000             jmp 0x00007fd20438c1b6
        ;; B16
        ;; ParallelMove r9 <- rax, rax <- r12 goto:182 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c1a5    4989c1                 movq r9,rax
0x7fd20438c1a8    4c89e0                 movq rax,r12
0x7fd20438c1ab    e906000000             jmp 0x00007fd20438c1b6
        ;; B15
        ;; ParallelMove r9 <- rax, rax <- r10 goto:178 B14
        ;; Inlined [::.tableLookup]
0x7fd20438c1b0    4989c1                 movq r9,rax
0x7fd20438c1b3    4c89d0                 movq rax,r10
        ;; B14
        ;; StoreField(v2 T{Reproduction} . byteOffset = v19 T{int} <int64>)
        ;; Inlined [::.tableLookup]
0x7fd20438c1b6    4c894f17               movq [rdi+0x17],r9
        ;; ParallelMove rax <- rax
        ;; DartReturn:220(v20)

Note that some moves are different.

Corresponding part of the flow graph:

144: B24[target]:212
146:     ParallelMove r9 <- r9, rax <- rbx goto:214 B14
148: B23[target]:208
150:     ParallelMove r9 <- rax, rax <- rbx goto:210 B14
152: B22[target]:204
154:     ParallelMove r9 <- rax, rax <- rbx goto:206 B14
156: B21[target]:200
158:     ParallelMove r9 <- rax, rax <- rbx goto:202 B14
160: B20[target]:196
162:     ParallelMove r9 <- rax, rax <- rbx goto:198 B14
164: B19[target]:192
166:     ParallelMove r9 <- rax, rax <- rbx goto:194 B14
168: B18[target]:188
170:     ParallelMove r9 <- rax, rax <- rbx goto:190 B14
172: B17[target]:184
174:     ParallelMove r9 <- rax, rax <- r13 goto:186 B14
176: B16[target]:180
178:     ParallelMove r9 <- rax, rax <- r12 goto:182 B14
180: B15[target]:176
182:     ParallelMove r9 <- rax, rax <- r10 goto:178 B14
184: B14[join]:174 pred(B15, B16, B17, B18, B19, B20, B21, B22, B23, B24) {
      v19 <- phi(v16 T{int}, v22 T{int}, v26 T{int}, v30 T{int}, v34 T{int}, v38 T{int}, v42 T{int}, v46 T{int}, v50 T{int}, v54 T{int}) alive [0, v300-1] int64 T{int}
      v20 <- phi(v340 T{_Smi}, v343 T{_Smi}, v345 T{_Smi}, v347 T{_Smi}, v349 T{_Smi}, v351 T{_Smi}, v353 T{_Smi}, v355 T{_Smi}, v357 T{_Smi}, v359 T{_Smi}) alive [0, 255] int64 T{_Smi}
}       
186:     StoreField(v2 T{Reproduction} . byteOffset = v19 T{int} <int64>)
188:     DartReturn:220(v20)

Due to repeated tableLookup(next = bytes[++localByteOffset]) && code there are multiple similar comparisons which branch to almost empty basic blocks B15-B24, which only do ParallelMove and then jump to the same block B14. B14 has a phi which joins values from all blocks (localByteOffset and next). Those ParallelMove instructions are used to implement phis in B14 - they move values between registers from the locations specific to source blocks to the location specific to the destination block. Note that they are slightly different, and only some of those moves are exactly the same. If those blocks would not have ParallelMove, they would be eliminated by the compiler.

So I can conclude that this repeated generated code is largely a consequence of the repeated source code and somewhat sub-optimal register allocation.

Maybe it is possible to improve register allocator to always allocate those values on the same registers in the preceding blocks so ParallelMove instructions would not be needed here (@mraleph WDYT?). We can also think about some kind of deduplication of basic blocks with the same code to reduce size of the repeated code, which could be useful in the cases like this or when source code is auto-generated.

[ykmnkmi]

Just a question: is that related to a HTTP parser?

[a-siva]

Just a question: is that related to a HTTP parser?

No it is not related to a HTTP parser.