Arithmetic shift by an unsigned value of type bit<W>

[jaehyun1ee]

The spec mentions about arithmetic shifts in 8.8. Operations on arbitrary-precision integers that:

Arithmetic shift left and right denoted by << and >>. These operations produce an int result. The right operand must be either an unsigned value of type bit<W> or a compile-time known value that is a non-negative integer.

However, p4c rejects program issue2206.p4 and shitf-int-non-const.p4, requiring that the right operand of type bit<W> should be compile-time known. (according to the spec, the condition compile-time known is necessary when the type is not bit<W>)

// issue2206.p4

header H {
    bit<8> a;
    bit<8> b;
    bit<8> c;
}

struct Headers {
    H   h;
}

control ingress(inout Headers h, inout Meta m, inout standard_metadata_t sm) {
    apply {
        h.h.a = (1 << h.h.c) + 8w2; // h.h.c has type bit<8>, so it need not be compile-time known
    }
}

// issue2206.p4(27): [--Werror=type-error]
// error: 1 << h.h.c: shift result type is arbitrary-precision int, but right operand is not constant;
// width of left operand of shift needs to be specified or both operands need to be constant

// shift-int-non-const.p4

header hdr_t {
  bit<8> v;
}

control c(inout hdr_t hdr, inout bit<4> b) {
  apply {
    const int a = 5;
    hdr.v = (bit<8>)(a >> b); // b has type bit<4>, so it need not be compile-time known
  }
}

// shift-int-non-const.p4(8): [--Werror=type-error]
// error: 5 >> b: shift result type is arbitrary-precision int, but right operand is not constant;
// width of left operand of shift needs to be specified or both operands need to be constant

[ChrisDodd]

Ugh, this is nasty. I think the spec was written to embody what is easily implementable in the compiler, but this is getting tough.

The problem is that we don't have a good way of dealing with an arbitrary precision value (an int) which is NOT compile-time know. For compile-time know values, it is just an IR::Constant (internally, a cpp_int), but for anything else we'd need to deal with it symbolically and ensure it wouldn't get to the backend (as any backend will balk at trying to deal with arbitrary precision ints).

This means pushing the type "down" from the context (so in these cases, note that the result is cast to bit<8> so use that.) But that fails for more complex cases like

bit<8> x = (1 << a) >> b;

where a and b are not compile-time known. We'd need to create something like:

bit<8> x = (a < b || a + 8 >= b) ? 0 : 8w1 << (a - b);

and if there are any other operations involved in the expression it gets even worse.

[vlstill]

I think this is prohibited by this leading text in 8.8. Operations on arbitrary-precision integers:

The type int denotes arbitrary-precision integers. In P4, all expressions of type int must be compile-time known values. The type int supports the following operations:

However, in your example, (1 << h.h.c) or (bit<8>)(a >> b) is not compile-time known. Therefore, the programmer would be (rightly, in my opinion) forced to write e.g. 8w1 << h.h.c or ((bit<8>)a) >> b respectively.

[jaehyun1ee]

@vlstill Thank you for pointing it out :) I believe it explains why the programs should be rejected.