google / xls Goto Github PK

case A:
case B:
dostuff();
break;

Seems like a parser order of operations problem.

right:
if((state.cnt.slc<3>(8)) != 0) {

wrong:
if(state.cnt.slc<3>(8) != 0) {

In VAST we currently special cast single bit reg/wires when defining and indexing:

This produces:

wire foo;

instead of:

wire [0:0] foo;

and avoids invalid indexing of a widthless (single bit) wire/reg. However, it would be cleaner and less surprising if VAST didn't magically do this transformation under the hood. This belongs at a higher abstraction level such as modulebuilder.

State state;
if(state == State_TX)..

Produces weird bit-slice error from XLS. XLS[cc] should instead catch this.

F0630 09:37:42.085735 23279 codegen_main.cc:221] Check failed: ::absl::OkStatus() == (xls::RealMain(ir_path, absl::GetFlag(FLAGS_output_verilog_path), absl::GetFlag(FLAGS_output_signature_path), absl::GetFlag(FLAGS_output_schedule_path))) (OK vs. UNIMPLEMENTED: Unsupported array-shaped op: sel.189: bits[2][2] = sel(tuple_index.61, cases=[tuple_index.106, literal.163], pos=0,28,5))

Original IR:

package test_package

fn Run(swregs: (bits[1]), ctrl_in_vz: bits[1], ctrl_in_z: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]), cavlc_out_vz: bits[1], cabac_out_vz: bits[1]) -> (bits[1], bits[1], (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]), bits[1], (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1])) {
literal.62: bits[32] = literal(value=0, pos=0,27,44)
tuple_index.61: bits[1] = tuple_index(swregs, index=0, pos=0,27,7)
bit_slice.63: bits[1] = bit_slice(literal.62, start=0, width=1, pos=0,27,44)
literal.9: bits[2] = literal(value=0, pos=0,22,6)
literal.14: bits[5] = literal(value=0, pos=0,22,6)
literal.16: bits[5] = literal(value=0, pos=0,22,6)
literal.18: bits[5] = literal(value=0, pos=0,22,6)
literal.20: bits[5] = literal(value=0, pos=0,22,6)
literal.22: bits[5] = literal(value=0, pos=0,22,6)
literal.24: bits[5] = literal(value=0, pos=0,22,6)
literal.37: bits[2] = literal(value=0, pos=0,22,6)
literal.42: bits[5] = literal(value=0, pos=0,22,6)
literal.44: bits[5] = literal(value=0, pos=0,22,6)
literal.46: bits[5] = literal(value=0, pos=0,22,6)
literal.48: bits[5] = literal(value=0, pos=0,22,6)
literal.50: bits[5] = literal(value=0, pos=0,22,6)
literal.52: bits[5] = literal(value=0, pos=0,22,6)
eq.64: bits[1] = eq(tuple_index.61, bit_slice.63, pos=0,27,7)
literal.3: bits[1] = literal(value=0, pos=0,22,6)
literal.7: bits[2] = literal(value=0, pos=0,22,6)
literal.8: bits[5] = literal(value=0, pos=0,22,6)
array.10: bits[2][2] = array(literal.9, literal.9, pos=0,22,6)
literal.11: bits[2] = literal(value=0, pos=0,22,6)
literal.12: bits[1] = literal(value=0, pos=0,22,6)
literal.13: bits[1] = literal(value=0, pos=0,22,6)
array.15: bits[5][4] = array(literal.14, literal.14, literal.14, literal.14, pos=0,22,6)
array.17: bits[5][2] = array(literal.16, literal.16, pos=0,22,6)
array.19: bits[5][2] = array(literal.18, literal.18, pos=0,22,6)
array.21: bits[5][4] = array(literal.20, literal.20, literal.20, literal.20, pos=0,22,6)
array.23: bits[5][2] = array(literal.22, literal.22, pos=0,22,6)
array.25: bits[5][2] = array(literal.24, literal.24, pos=0,22,6)
literal.26: bits[1] = literal(value=0, pos=0,22,6)
literal.27: bits[1] = literal(value=0, pos=0,22,6)
literal.28: bits[1] = literal(value=0, pos=0,22,6)
literal.29: bits[1] = literal(value=0, pos=0,22,6)
literal.30: bits[1] = literal(value=0, pos=0,22,6)
literal.31: bits[1] = literal(value=0, pos=0,22,6)
literal.35: bits[2] = literal(value=0, pos=0,22,6)
literal.36: bits[5] = literal(value=0, pos=0,22,6)
array.38: bits[2][2] = array(literal.37, literal.37, pos=0,22,6)
literal.39: bits[2] = literal(value=0, pos=0,22,6)
literal.40: bits[1] = literal(value=0, pos=0,22,6)
literal.41: bits[1] = literal(value=0, pos=0,22,6)
array.43: bits[5][4] = array(literal.42, literal.42, literal.42, literal.42, pos=0,22,6)
array.45: bits[5][2] = array(literal.44, literal.44, pos=0,22,6)
array.47: bits[5][2] = array(literal.46, literal.46, pos=0,22,6)
array.49: bits[5][4] = array(literal.48, literal.48, literal.48, literal.48, pos=0,22,6)
array.51: bits[5][2] = array(literal.50, literal.50, pos=0,22,6)
array.53: bits[5][2] = array(literal.52, literal.52, pos=0,22,6)
literal.54: bits[1] = literal(value=0, pos=0,22,6)
literal.55: bits[1] = literal(value=0, pos=0,22,6)
literal.56: bits[1] = literal(value=0, pos=0,22,6)
literal.57: bits[1] = literal(value=0, pos=0,22,6)
literal.58: bits[1] = literal(value=0, pos=0,22,6)
literal.59: bits[1] = literal(value=0, pos=0,22,6)
not.68: bits[1] = not(eq.64, pos=0,27,3)
sel.67: bits[1] = sel(eq.64, cases=[literal.3, cavlc_out_vz], pos=0,28,5)
literal.6: bits[1] = literal(value=0, pos=0,22,6)
tuple.32: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]) = tuple(literal.7, literal.8, array.10, literal.11, literal.12, literal.13, array.15, array.17, array.19, array.21, array.23, array.25, literal.26, literal.27, literal.28, literal.29, literal.30, literal.31, pos=0,22,6)
literal.34: bits[1] = literal(value=0, pos=0,22,6)
tuple.60: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]) = tuple(literal.35, literal.36, array.38, literal.39, literal.40, literal.41, array.43, array.45, array.47, array.49, array.51, array.53, literal.54, literal.55, literal.56, literal.57, literal.58, literal.59, pos=0,22,6)
sel.71: bits[1] = sel(not.68, cases=[sel.67, cabac_out_vz], pos=0,30,5)
sel.66: bits[1] = sel(eq.64, cases=[literal.6, ctrl_in_vz], pos=0,28,5)
sel.65: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]) = sel(eq.64, cases=[tuple.32, ctrl_in_z], pos=0,28,5)
sel.70: bits[1] = sel(not.68, cases=[literal.34, ctrl_in_vz], pos=0,30,5)
sel.69: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]) = sel(not.68, cases=[tuple.60, ctrl_in_z], pos=0,30,5)
ret tuple.72: (bits[1], bits[1], (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]), bits[1], (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1])) = tuple(sel.71, sel.66, sel.65, sel.70, sel.69, pos=0,22,6)
}

It's convenient to have a shorthand notation for "deeper path" updates, say to a struct that carries nuanced data from "tick" to "tick" (which ultimately is state since it iterates in time, even though we don't mutate it). I was thinking of this shorthand syntax -- it'd be convenient to do something like:

s.data[foo][bar] := u32:42;

which would basically do:

let s = State{data: update(s.data, foo, update(s.data[foo], bar, u32:42)), ..s};

as a desugaring so you don't need to write it all out. Note that this operator is rebinding the "outermost" referenced identifier (in the scope in which it's written).

This would be useful for getting some idea of how long we should expect some proofs to take - it's at least a necessary first step.

Really we should add generation of match constructs to the fuzzer. Found a bug in single-arm matches (just a single wildcard arm) where the JIT miscompares with the DSL.

This line causes an error:

assign eq_64 = swregs[0:0] == literal_62[0];

Generate command:

bazel-bin/xls/tools/codegen_main ~/tmp/test.ir --generator=combinational

From IR:

package test_package

fn Run(swregs: (bits[1]), ctrl_in_vz: bits[1], ctrl_in_z: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]), cavlc_out_vz: bits[1], cabac_out_vz: bits[1]) -> (bits[1], bits[1], (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]), bits[1], (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1])) {
literal.62: bits[32] = literal(value=0, pos=0,27,44)
tuple_index.61: bits[1] = tuple_index(swregs, index=0, pos=0,27,7)
bit_slice.63: bits[1] = bit_slice(literal.62, start=0, width=1, pos=0,27,44)
literal.9: bits[2] = literal(value=0, pos=0,22,6)
literal.14: bits[5] = literal(value=0, pos=0,22,6)
literal.16: bits[5] = literal(value=0, pos=0,22,6)
literal.18: bits[5] = literal(value=0, pos=0,22,6)
literal.20: bits[5] = literal(value=0, pos=0,22,6)
literal.22: bits[5] = literal(value=0, pos=0,22,6)
literal.24: bits[5] = literal(value=0, pos=0,22,6)
literal.37: bits[2] = literal(value=0, pos=0,22,6)
literal.42: bits[5] = literal(value=0, pos=0,22,6)
literal.44: bits[5] = literal(value=0, pos=0,22,6)
literal.46: bits[5] = literal(value=0, pos=0,22,6)
literal.48: bits[5] = literal(value=0, pos=0,22,6)
literal.50: bits[5] = literal(value=0, pos=0,22,6)
literal.52: bits[5] = literal(value=0, pos=0,22,6)
eq.64: bits[1] = eq(tuple_index.61, bit_slice.63, pos=0,27,7)
literal.3: bits[1] = literal(value=0, pos=0,22,6)
literal.7: bits[2] = literal(value=0, pos=0,22,6)
literal.8: bits[5] = literal(value=0, pos=0,22,6)
array.10: bits[2][2] = array(literal.9, literal.9, pos=0,22,6)
literal.11: bits[2] = literal(value=0, pos=0,22,6)
literal.12: bits[1] = literal(value=0, pos=0,22,6)
literal.13: bits[1] = literal(value=0, pos=0,22,6)
array.15: bits[5][4] = array(literal.14, literal.14, literal.14, literal.14, pos=0,22,6)
array.17: bits[5][2] = array(literal.16, literal.16, pos=0,22,6)
array.19: bits[5][2] = array(literal.18, literal.18, pos=0,22,6)
array.21: bits[5][4] = array(literal.20, literal.20, literal.20, literal.20, pos=0,22,6)
array.23: bits[5][2] = array(literal.22, literal.22, pos=0,22,6)
array.25: bits[5][2] = array(literal.24, literal.24, pos=0,22,6)
literal.26: bits[1] = literal(value=0, pos=0,22,6)
literal.27: bits[1] = literal(value=0, pos=0,22,6)
literal.28: bits[1] = literal(value=0, pos=0,22,6)
literal.29: bits[1] = literal(value=0, pos=0,22,6)
literal.30: bits[1] = literal(value=0, pos=0,22,6)
literal.31: bits[1] = literal(value=0, pos=0,22,6)
literal.35: bits[2] = literal(value=0, pos=0,22,6)
literal.36: bits[5] = literal(value=0, pos=0,22,6)
array.38: bits[2][2] = array(literal.37, literal.37, pos=0,22,6)
literal.39: bits[2] = literal(value=0, pos=0,22,6)
literal.40: bits[1] = literal(value=0, pos=0,22,6)
literal.41: bits[1] = literal(value=0, pos=0,22,6)
array.43: bits[5][4] = array(literal.42, literal.42, literal.42, literal.42, pos=0,22,6)
array.45: bits[5][2] = array(literal.44, literal.44, pos=0,22,6)
array.47: bits[5][2] = array(literal.46, literal.46, pos=0,22,6)
array.49: bits[5][4] = array(literal.48, literal.48, literal.48, literal.48, pos=0,22,6)
array.51: bits[5][2] = array(literal.50, literal.50, pos=0,22,6)
array.53: bits[5][2] = array(literal.52, literal.52, pos=0,22,6)
literal.54: bits[1] = literal(value=0, pos=0,22,6)
literal.55: bits[1] = literal(value=0, pos=0,22,6)
literal.56: bits[1] = literal(value=0, pos=0,22,6)
literal.57: bits[1] = literal(value=0, pos=0,22,6)
literal.58: bits[1] = literal(value=0, pos=0,22,6)
literal.59: bits[1] = literal(value=0, pos=0,22,6)
not.68: bits[1] = not(eq.64, pos=0,27,3)
sel.67: bits[1] = sel(eq.64, cases=[literal.3, cavlc_out_vz], pos=0,28,5)
literal.6: bits[1] = literal(value=0, pos=0,22,6)
tuple.32: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]) = tuple(literal.7, literal.8, array.10, literal.11, literal.12, literal.13, array.15, array.17, array.19, array.21, array.23, array.25, literal.26, literal.27, literal.28, literal.29, literal.30, literal.31, pos=0,22,6)
literal.34: bits[1] = literal(value=0, pos=0,22,6)
tuple.60: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]) = tuple(literal.35, literal.36, array.38, literal.39, literal.40, literal.41, array.43, array.45, array.47, array.49, array.51, array.53, literal.54, literal.55, literal.56, literal.57, literal.58, literal.59, pos=0,22,6)
sel.71: bits[1] = sel(not.68, cases=[sel.67, cabac_out_vz], pos=0,30,5)
sel.66: bits[1] = sel(eq.64, cases=[literal.6, ctrl_in_vz], pos=0,28,5)
sel.65: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]) = sel(eq.64, cases=[tuple.32, ctrl_in_z], pos=0,28,5)
sel.70: bits[1] = sel(not.68, cases=[literal.34, ctrl_in_vz], pos=0,30,5)
sel.69: (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]) = sel(not.68, cases=[tuple.60, ctrl_in_z], pos=0,30,5)
ret tuple.72: (bits[1], bits[1], (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1]), bits[1], (bits[2], bits[5], bits[2][2], bits[2], bits[1], bits[1], bits[5][4], bits[5][2], bits[5][2], bits[5][4], bits[5][2], bits[5][2], bits[1], bits[1], bits[1], bits[1], bits[1], bits[1])) = tuple(sel.71, sel.66, sel.65, sel.70, sel.69, pos=0,22,6)
}

Found this while testing #66.

For what it's worth, the problematic function is run_instruction() and we manged to trace the execution in gdb up until it actually runs the compiled function. After that, we don't have any debugging symbols to use so we're stuck with reading assembly.

For now, I set compare_jit=False in examples/BUILD.

OK to error out when it's not power-of-two.

These may only be present in unopt builds, but we still want to be able to JIT compile unopt IR. Simplest example I believe is:

concat.1: bits[0] = concat()

For now I'll just say max(bit_count, 1) to avoid making LLVM assertion fail in the type conversion.

I'm adding quick hack support for FuncDecls right now, but the original XLS[cc] had broad support in all names. It should be possible with the plycparser.

void reverse_nibbles(sai16 &x) {
#pragma hls_unroll yes
for(int b=0;b<16;b+=4) {
x.set_slc(b, x.slc<4>(12-b));
}
}

Wrote a DSLX test that had a divide in it and got the following:

F0611 15:14:56.103664 3599 check_ir_equivalence_main.cc:161] Check failed: ::absl::OkStatus() == (xls::RealMain(positional_args, absl::GetFlag(FLAGS_function), absl::GetFlag(FLAGS_timeout))) (OK vs. UNIMPLEMENTED: Unhandled node for conversion: udiv.32: bits[32] = udiv(shrl.76, literal.27, pos=0,18,40))

I think we may be able to lower udiv into this bvudiv? Z3Prover/z3#1786

This was for the unopt version so it should have strength reduced after optimization, but the pre-optimized IR gets fed to the equivalence checker as well as the optimized IR I believe. Could write a test that a udiv by 4 was the same as a shr 2 as a test case.

It's the clang-format era, gotta have one!

xlscc supports arbitrary bit widths for the generated hardware, but not in the software model.

Requires a dependency on https://github.com/hlslibs/ac_types

@cdleary said we got a feature request! Something like..

fn [X: u32] foo() -> u32 {
     X
}

fn bar() -> u32 {
     foo[u32: 5]()
}

With quickcheck landing we should be able to use that as a straightforward example use of quickcheck functionality (array concatenate operator).

Looks like the repl hasn't been kept up with in a while. I think repls are great for playing with language features and for newcomers to use while reading through intro docs! Here are some top level issues that I found but deeper investigation is needed:

• The repl should probably just ignore empty input (hitting enter a few times to space out expressions). currently crashes with what looks like an unexpected eof error
• Basic expressions don't seem to work. Here's the trace I got after feeding in a simple let expression:

dslx> let x = u32: 5 in x
Traceback (most recent call last):
  File "/home/hans/.cache/bazel/_bazel_hans/86fbd19228f075342ea6524b7249e353/execroot/com_google_xls/bazel-out/k8-opt/bin/xls/dslx/interpreter/./repl.runfiles/com_google_xls/xls/dslx/interpreter/repl.py", line 118, in <module>
    app.run(main)
  File "/home/hans/.cache/bazel/_bazel_hans/86fbd19228f075342ea6524b7249e353/execroot/com_google_xls/bazel-out/k8-opt/bin/xls/dslx/interpreter/repl.runfiles/com_google_absl_py/absl/app.py", line 299, in run
    _run_main(main, args)
  File "/home/hans/.cache/bazel/_bazel_hans/86fbd19228f075342ea6524b7249e353/execroot/com_google_xls/bazel-out/k8-opt/bin/xls/dslx/interpreter/repl.runfiles/com_google_absl_py/absl/app.py", line 250, in _run_main
    sys.exit(main(argv))
  File "/home/hans/.cache/bazel/_bazel_hans/86fbd19228f075342ea6524b7249e353/execroot/com_google_xls/bazel-out/k8-opt/bin/xls/dslx/interpreter/./repl.runfiles/com_google_xls/xls/dslx/interpreter/repl.py", line 100, in main
    concrete_type_to_annotation(result_type),
  File "/home/hans/.cache/bazel/_bazel_hans/86fbd19228f075342ea6524b7249e353/execroot/com_google_xls/bazel-out/k8-opt/bin/xls/dslx/interpreter/./repl.runfiles/com_google_xls/xls/dslx/interpreter/repl.py", line 49, in concrete_type_to_annotation
    if concrete_type.is_bits():
AttributeError: 'BitsType' object has no attribute 'is_bits'

We can interpret them for arbitrary right hand sides in the interpreter, but by default we should probably only lower it successfully in IR conversion if the RHS is a "constexpr" power of two, because instantiating divide units is extremely unweildy and should probably require some sort of opt-in indicator from the user.

Command run:

bazel test -c opt ...

Output:

bazel-out/k8-opt-exec-2B5CBBC6/bin/external/clang_binaries/clang_format: error while loading shared libraries: libtinfo.so.5: cannot open shared object file: No such file or directory

$ ldd bazel-out/k8-opt-exec-2B5CBBC6/bin/external/clang_binaries/clang_format
        linux-vdso.so.1 (0x00007ffdf21f7000)
        libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007fc81e981000)
        librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007fc81e976000)
        libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007fc81e970000)
        libtinfo.so.5 => not found
        libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007fc81e821000)
        libstdc++.so.6 => /lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007fc81e640000)
        libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007fc81e623000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fc81e431000)
        /lib64/ld-linux-x86-64.so.2 (0x00007fc81e9b8000)
$ locate libtinfo
...
/snap/core18/1705/lib/x86_64-linux-gnu/libtinfo.so.5
/snap/core18/1705/lib/x86_64-linux-gnu/libtinfo.so.5.9
...
/usr/lib/x86_64-linux-gnu/libtinfo.so.6
/usr/lib/x86_64-linux-gnu/libtinfo.so.6.2
...
$ dpkg --list | grep libtinfo
ii  libtinfo6:amd64                            6.2-0ubuntu2                               amd64        shared low-level terminfo library for terminal handling
$ apt-cache search libtinfo
libncurses-dev - developer's libraries for ncurses
libtinfo-dev - transitional package for libncurses-dev
libtinfo6 - shared low-level terminfo library for terminal handling
libtinfo5 - shared low-level terminfo library (legacy version)

So we likely need to update the installation instructions to tell users to install libtinfo5 given the current clang-format binary build, this issue serves as a reminder.

DSLX input:

import std

const A = u32[3]:[10, 20, 30];

fn main(i: u32) -> u32 {
  std::find_index(A, i)
}

See attached image for IR graph. Ideally this should lower into something like a concat of eq's feeding an encode. Of particular concern is the multiple array update and array index operations which end up copying the array multiple times. The array issue is fallout from adding the arrayupdate operation.

Optimized IR:

package foo
fn __xls_tempfile_4ulpjD__main(i: bits[32]) -> (bits[1], bits[32]) {
  literal.229: bits[32] = literal(value=10, pos=0,74,26)
  literal.168: bits[1][3] = literal(value=[0, 0, 0], pos=0,75,17)
  literal.165: bits[32] = literal(value=0, pos=0,73,30)
  eq.169: bits[1] = eq(i, literal.229, pos=0,74,30)
  literal.230: bits[32] = literal(value=20, pos=0,74,26)
  array_update.172: bits[1][3] = array_update(literal.168, literal.165, eq.169, pos=0,74,10)
  literal.167: bits[32] = literal(value=1, pos=0,73,30)
  eq.173: bits[1] = eq(i, literal.230, pos=0,74,30)
  literal.231: bits[32] = literal(value=30, pos=0,74,26)
  array_update.175: bits[1][3] = array_update(array_update.172, literal.167, eq.173, pos=0,74,10)
  literal.171: bits[32] = literal(value=2, pos=0,73,30)
  eq.176: bits[1] = eq(i, literal.231, pos=0,74,30)
  array_update.179: bits[1][3] = array_update(array_update.175, literal.171, eq.176, pos=0,74,10)
  literal.257: bits[32] = literal(value=0, pos=0,73,30)
  literal.258: bits[32] = literal(value=1, pos=0,73,30)
  literal.259: bits[32] = literal(value=2, pos=0,73,30)
  array_index.184: bits[1] = array_index(array_update.179, literal.257, pos=0,53,13)
  literal.260: bits[2] = literal(value=0, pos=0,53,27)
  literal.250: bits[1] = literal(value=0, pos=0,53,27)
  array_index.193: bits[1] = array_index(array_update.179, literal.258, pos=0,53,13)
  literal.261: bits[1] = literal(value=0, pos=0,53,27)
  literal.238: bits[2] = literal(value=0, pos=0,53,27)
  array_index.203: bits[1] = array_index(array_update.179, literal.259, pos=0,53,13)
  concat.248: bits[3] = concat(array_index.184, literal.260, pos=0,53,27)
  concat.249: bits[3] = concat(literal.250, array_index.193, literal.261, pos=0,53,27)
  concat.208: bits[3] = concat(literal.238, array_index.203, pos=0,53,13)
  or.244: bits[3] = or(concat.248, concat.249, concat.208, pos=0,53,9)
  reverse.213: bits[3] = reverse(or.244, pos=0,78,17)
  one_hot.214: bits[4] = one_hot(reverse.213, lsb_prio=true, pos=0,78,17)
  encode.215: bits[2] = encode(one_hot.214)
  literal.216: bits[2] = literal(value=3, pos=0,79,30)
  literal.217: bits[30] = literal(value=0, pos=0,80,10)
  ne.218: bits[1] = ne(encode.215, literal.216, pos=0,79,26)
  concat.219: bits[32] = concat(literal.217, encode.215, pos=0,80,10)
  sign_ext.220: bits[32] = sign_ext(ne.218, new_bit_count=32, pos=0,80,23)
  and.221: bits[32] = and(concat.219, sign_ext.220, pos=0,80,23)
  ret tuple.222: (bits[1], bits[32]) = tuple(ne.218, and.221, pos=0,80,2)
}

Right now we don't take into account that the type being checked in the assertion is signed.

* 0119:   let _ = assert_eq(s11:-293, extract_coeff(u9:0xda ++ u2:0, u4:9));
        ~~~~~~~~~~~~~~~~~~~^----------------------------------------------^ The program being interpreted failed! 
  want: 1755
  got:  1

Right now you get a difficult to read value since they types are all presented inline, instead of factored out; i.e.

  want: [bits[32]:0x2, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x2, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x2, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x2, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x2, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x2, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x2, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x2, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3, bits[32]:0x3]

This will require us to a) translate the functions under test (those called from the unit test code) into converted IR and, b) run them via the JIT, by way of the Python bindings (so we can reuse the existing test enumeration code that is written in Python).

Right now:

const WIDTH_IN_BYTES = u32:4;
const DERIVED_VALUE = u32:4*WIDTH_IN_BYTES;

gives an error because the multiplication expression is not a simple constant. We can probably support arbitrary expressions in this position since no synthesizable function/expression is turing complete.

XLS holds its data in big-endian sort of format, where Bits::Get(0) will return the MSb. Z3 holds data in little-endian format.

This has caused me tremendous headaches; if we defined a more formal way of translating values between the two contexts, that'd probably save me a lot of headaches.

Out-of-bounds ArrayIndex operations clamp the index to the highest element:

Out-of-bounds ArrayUpdate operations are noops:

This is not very consistent because we clamp only in the ArrayIndex case. We should think about what semantics we want here. One option is to make OOB ArrayIndex return the zero value. Alternatively OOB behavior could be configurable.

Found two issues via QuickCheck:

This segfaults (which is weird because just xs == ys doesn't segfault):

#![quickcheck]
fn prop_commutative(xs: u32[2], ys: u32[2]) -> bool {
  (xs == ys) || ((xs ++ ys) != (ys ++ xs))
}

This returns an incorrect falsifying example:

[ RUN QUICKCHECK   ] prop_commutative
concat.x:1-6
  0001: #![quickcheck]
* 0002: fn prop_commutative(xs: u32[1], ys: u32[1]) -> bool {
        ^^ Found falsifying example after 1 tests: ['[bits[32]:0xb3aa_8983]', '[bits[32]:0x2ae6_decb]']
  0003:   (xs ++ ys) != (ys ++ xs)
  0004: }
[           FAILED ] prop_commutative FailureError

Rust chooses shra or shrl depending on the signedness of the integer being shifted, see the footnote here: https://doc.rust-lang.org/reference/expressions/operator-expr.html#arithmetic-and-logical-binary-operators

Right now we have >> for logical and >>> for arithmetic, as a vestige from earlier times (now we try to follow Rust syntax as closely as is reasonably possible).

/cc @hmontero1205

Keeping the configs in a normalized list has some advantages, but if we keep it that way it has to be documented since it doesn't follow the traditional name = "foo" producing only foo as a target kind of behavior.

Also we should probably aggregate all those targets into a list under the dslx_codegen name if we don't do that already, so building that one target builds all the configs.

Currently we emit an error like:

"Output out, instance #0 not found in Verilog simulator output".

We should raise an error indicating that there was an X in the output until we handle X properly (if ever).

For very-high throughput cases, we need to avoid the input marshalling overhead (allocating arg buffer storage, blitting elements of input XLS IR Values to that buffer - which needs even more intermediate storage (see Bits::ToBytes)).

Building with gcc-8, I received an error of undefined reference to 'std::filesystem::__cxx11::path::_M_split_cmpts()'. Maybe it needs a flag?

RIght now I have to write:

SomeStruct d;
out = x;

I should be able to write:

out = SomeStruct();

--vmodule=${source_file}=${N} should enable VLOG messages at level ${N} or lower for the source file named ${source_file}, but it does not work in tests. -v=N does nothing either.

Seems to work in non-test binaries. Likely the underlying cause is that InitXls is not being called in tests (?). May need to define a common base class which calls InitXls and derive XLS tests from that class.

cc @hmontero1205

In #70 support for quickchecking non-parametric functions is introduced -- we'll want a way to let the quickcheck "driver" instantiate parametric functions with the ability to put constraints on the parametric values. One nice aspect of this is the quickcheck driver can use normal functions to test properties of normal values (e.g. filtering via is_even as a predicate on a given parametric N: u32) and then use that value to drive the instantiation. This will make the quickcheck less vectorizable, but we can vector-test some number of samples for any given parametric N chosen to get some batch efficiency.

cc @meheff We can desugar them in the frontend for now but it makes the graph unnecessarily bloated, could be good first bug?

DSL started off more Python-like but now we're going to try to be as close to Rust as is reasonable -- the current parser is currently all recursive descent (no "precedence climbing") so changing the precedence rules amounts to changing the recursive call structure. Keywords like "and", "or", "not" turn to their C-like equivalents.

This is a good first bug for getting familiar with the frontend.

A warning in the frontend (e.g. as determined at type checking time) could make some sense perhaps if we detect the splat is useless?

Originally posted by @cdleary in #52

e.g. in the case where all fields are clobbered, such as:

struct Point {
  x: u32
  y: u32
}
fn f(p: Point) -> Point {
  Point{x: u32:42, y: u32:42, ...p}  // <- this splat is useless
}

ParseError:
int dbg_en = state.cnt < 75;

Works:
uai32 x = state.cnt;
int dbg_en = x < 75;

As per #46 (comment), we need to find a better way to return to the typecheck stack. Currently, we ensure that f.body is always removed after typechecking a parametric function so that we can reraise this exception when we need to recheck the body in the context of different bindings.

Internally we use pytype rules that enforce type checking, but we haven't yet set them up for open source export (which will really be a bidirectional sync soon).

It's often convenient to support (simple) expressions that are a) derived from parametric bindings that b) can be used in parametric positions in the function signature; e.g.

// Doubles the width of the given value.
fn [X: u32, Y: u32 = X+X] double_width(x: bits[X]) -> bits[Y] {
  bits[Y]:x
}

This also raises the question of whether the "derived parametrics" can be used as checked constraints on how the function is instantiated:

// Causes a type error if Y is not equal to double X at the point(s) of instantiation.
fn [X: u32, Y: u32 = X+X] check_double_width(x: bits[X], y: bits[Y]) -> () {
  ()
}

Thinking about a test matrix might be useful, something like:

• direct instantiation w/integers, the simplest case we tend to think about
• instantiation w/symbols: a parametric function that delegates to another parametric function (that has different parametric symbols)
• derived parametric expressions, as shown before where some parametric symbols are given by expressions that require type-checking-time interpretation/evaluation

For use in all of: function parameters, "constraint" form (where different things use the same symbols and so have to be checked to be consistent), and return types.

rspringer@seitan:~/xls_github
$ bazel-bin/xls/dslx/interpreter/repl
dslx[0]> let x = bits[27]:0b001_1011_0000_0110_0110_1011_1101 in
/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/dslx/inte
rpreter/repl.py:75: DeprecationWarning: Call to deprecated function CreateFile. Use create_file instead.
fs.CreateFile(FILENAME, module_text)
Traceback (most recent call last):
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/interpreter/repl.py", line 81, in handle_line
FILENAME, module_text)).parse_module(fn_name)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 1233, in parse_module
parse_function(public=False)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 1204, in parse_function
f = self.parse_function(public, bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 1077, in parse_function
body = self.parse_expression(bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 965, in parse_expression
return self._parse_let(bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 404, in _parse_let
body = self.parse_expression(new_bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 970, in parse_expression
return self._parse_ternary_expression(bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 714, in _parse_ternary_expression
lhs = self._parse_logical_or_expression(bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 699, in _parse_logical_or_expression
(TokenKind.DOUBLE_BAR,), bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 695, in _parse_logical_and_expression
(TokenKind.DOUBLE_AMPERSAND,), bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 691, in _parse_comparison_expression
tuple(ast.Binop.COMPARISON_KINDS), bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 687, in _parse_or_expression
bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 683, in _parse_xor_expression
bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 679, in _parse_and_expression
(TokenKind.AMPERSAND,), bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 675, in _parse_bitwise_expression
_BITWISE_KINDS, bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 671, in _parse_weak_arithmetic_expression
_WEAK_ARITHMETIC_KINDS, bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
[ lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 667, in _parse_strong_arithmetic_expression
_STRONG_ARITHMETIC_KINDS, bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 647, in _parse_binop_chain
lhs = sub_production(*args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 659, in _parse_cast_as_expression
lhs = self._parse_term(bindings)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/parser.py", line 553, in _parse_term
'Expected start of an expression; got: {}'.format(tok.to_error_str()))
xls.dslx.parse_error.ParseError: Expected start of an expression; got: cbrace @ /fake/repl.x:5:3

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/interpreter/repl.py", line 157, in
app.run(main)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_absl_py/a
bsl/app.py", line 299, in run
_run_main(main, args)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_absl_py/a
bsl/app.py", line 250, in _run_main
sys.exit(main(argv))
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/interpreter/repl.py", line 149, in main
result = handle_line(line, stmt_index, f_import)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/interpreter/repl.py", line 83, in handle_line
parser_helpers.pprint_positional_error(e, fs_open=make_fakefs_open())
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/com_google_xls/xls/d
slx/interpreter/repl.py", line 75, in make_fakefs_open
fs.CreateFile(FILENAME, module_text)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/pyfakefs_archive/pyf
akefs/deprecator.py", line 50, in _new_func
return func(*args, **kwargs)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/pyfakefs_archive/pyf
akefs/deprecator.py", line 67, in _old_function
return func(*args, **kwargs)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/pyfakefs_archive/pyf
akefs/fake_filesystem.py", line 2340, in create_file
apply_umask, encoding, errors, side_effect=side_effect)
File "/usr/local/google/home/rspringer/xls_github/bazel-bin/xls/dslx/interpreter/repl.runfiles/pyfakefs_archive/pyf
akefs/fake_filesystem.py", line 2539, in create_file_internally
'st_mode must be of int type - did you mean to set contents?')
TypeError: st_mode must be of int type - did you mean to set contents?

That I don't know how to assign a var in the repl is a separate issue. :)

The operation slices a fixed width value at a dynamic offset.

mnemonics:
dynamic_bit_slice(x, y, width=W)

This returns a slice of 'x' which is 'W' bits wide (where 'W' is a constant) starting at offset 'y'. Any bits which are out of the bounds of 'x' are zero.

Steps:

(1) add Op and OpClass to https://github.com/google/xls/blob/master/xls/ir/op_specification.py Opcode should be 'kDynamicBitSlice'. This python generates the C++ .h and .cc file. This change will cause some build breakages due to switch statements expecting full coverage of enum values. Fix each of these.

(2) Add to function builder so you can build functions containing this op: https://github.com/google/xls/blob/master/xls/ir/function_builder.h

(3) Add to parser and verifier. Verifier should verify that the operands are bits-typed, and the width does not exceed the width of the sliced operand.

(4) Add to interpreter, and jit.

(5) Add to codegen: https://github.com/google/xls/blob/master/xls/codegen/node_expressions.h. Should use verilog '+:' slicing construct: foo[y +: W]

(6) Tie to front-end so DSLX uses dynamic bit slice operation: https://github.com/google/xls/blob/master/xls/dslx/ir_converter.py

To establish in the open source flow:

• use RBE for collaborative artifact caching
• make clang-format and buildifier and pyformat a single "fix" command
• standard presubmit command
• tricorder/linter
• asan(/msan/tsan?)/fastbuild testing modes via Kokoro

Our copybara rules are not all entirely reversible at the moment, this issues is to track our ability to get pull requests "back into" the downstream repository (by making all copybara rules completely reversible).

This is a blocker for accepting pull requests.

Right now each name must have a defined value:

enum Foo {
a=1,
b=2
};