DSLX interpreter hangs in simple loop

[ted-xie]

Minimal-ish example here.

interpreter_main donut.x will hang after the loop finishes all 256 iterations (last trace print statement shows the value of i as 0xff).

When I replace update(result_, u8:0, report_t:0) (line 49) with report_t[MAX_CYCLES]:[report_t:0, ...], the program finishes executing.

[ted-xie]

XLS git hash is 14d5f6e7ba1fd553cdfc9a0d5cb772c1c3ea75cf

[RobSpringer]

Looks like a hang in LLVM's register allocation:

Run till exit from #0  0x000055555e3ee595 in llvm::RegAllocBase::allocatePhysRegs (this=0x68f3f86a118)
    at llvm-project/llvm/lib/CodeGen/RegAllocBase.cpp:112
<hangs for a real long time, if not forever>

I'll see how much I can minimize the reproducer and open a bug on them.

[RobSpringer]

Really bizarre. Here's my reproducer:

If MAX_CYCLES is 86, it runs in about a second and a half. If it's 87, it hangs foreverrrr.

//const MAX_CYCLES = u32:86;  // 1.5 seconds
const MAX_CYCLES = u32:87;

fn foo() -> u1[MAX_CYCLES] {
  let result = for (i, result_): (u32, u1[MAX_CYCLES]) in range(u32:0, MAX_CYCLES) {
    update(result_, u8:0, u1:0)
  } (u1[MAX_CYCLES]:[u1:0, ...]);
  result
}

#![test]
fn main() {
    let _ = foo();
    ()
}

[RobSpringer]

Not forever - at MAX_CYCLES = 87 it takes 35 seconds. At 97, it takes 45 seconds. At 128, it takes 92, and at 192 it takes >300...so it's not a hang, just poor scaling past a threshold. I'll still report this to LLVM, and see if they want to do anything with it.

[cdleary]

I think @meheff's work on JIT scaling really helped the situation here. I wrote a hacky shell script and left it running a few minutes and wrote a hacky plot script while it was running:

for i in $(seq 1 1024); do perl -pe "s/u32:87/u32:${i}/" /tmp/test.x > /tmp/testn.x; echo "MAX_CYCLES=$i" >> /tmp/output.txt; /usr/bin/time -f '%e' bazel-bin/xls/dslx/interpreter_main /tmp/testn.x |& tee -a /tmp/output.txt; done

from operator import itemgetter
import fileinput
import re
from matplotlib import pyplot as plt

data = []
for line in fileinput.input():
  if line.startswith('['): continue
  m = re.search('MAX_CYCLES=(\d+)', line)
  if not m:
    y = float(line.strip())
    data.append((x, y))
    continue
  x = int(m.group(1))

unzip = lambda ps: (list(map(itemgetter(0), ps)), list(map(itemgetter(1), ps)))
plt.scatter(*unzip(data), marker='.')
plt.show()

And it shows this nice scaling curve now for the points I evaluated:

Something I guess starts getting aggregated at >1024, funny to see that little speedup bump.

[ted-xie]

Very nice, thanks @cdleary and @meheff!