Some for loops over range incorrectly use uninitialized values

[jafingerhut]

I tried a test P4 program (attached) using the for (typeRef var in min..max) style of loop, and believe the output IR from the compiler midend is subtly wrong in some cases, depending upon one's interpretation of the desired behavior.

Here is an example. A critical fact about the example is that the loop variable is modified within the body of the loop:

control c( /* ... */ ) {
    bit<8> n;
    apply {
        n = hdr.ethernet.dstAddr[7:0];
        for (bit<8> i in 1..n) {
            i = i + 1;
            n = n + i;
            hdr.ethernet.dstAddr[7:0] = hdr.ethernet.dstAddr[7:0] - 1;
        }
        hdr.ethernet.srcAddr[7:0] = n;
        stdmeta.egress_spec = 1;
    }
}

I believe that the behavior should be that the loop iterates exactly n times, where n is the original value of n when execution first reaches the for loop. The values of i during each successive iteration when hdr.ethernet.dstAddr[7:0] is equal to 3, for example, should be:

• 1, 2, 3

In particular, it should not skip an iteration with i equal to 2 because of the i = i + 1 statement in the loop body.

Note: It seems best to raise the question of the correct behavior in the LDWG if someone else's interpretation of the correct behavior for the oroginal program differs from mine above.

If my interpretation is correct, an equivalent way of writing the code above that I might hope to see in the output of midend is (see comments for special points of interest):

control c( /* ... */ ) {
    bit<8> n;
    bit<8> i_2;
    // Introducing loop_max1 in the frontend or midend code
    // is not necessary for correctness.  It would help simplify
    // backend code a bit.
    bit<8> loop_max1;
    apply {
        n = hdr.ethernet.dstAddr[7:0];
        loop_max1 = n;
        for (bit<8> i in 1..loop_max1) {
            // Note: all occurrences of i in the body except
            // the first have been replaced with i_2, just to
            // make it easier for a back end not to need
            // to create something like i_2 by itself.
            i_2 = i + 1;
            n = n + i_2;
            hdr.ethernet.dstAddr[7:0] = hdr.ethernet.dstAddr[7:0] - 1;
        }
        hdr.ethernet.srcAddr[7:0] = n;
        stdmeta.egress_spec = 1;
    }
}

With p4c built from 2024-Dec-30 version of the source code, this command:

mkdir -p tmp
p4test --dump tmp --top4 FrontEndLast,FrontEndDump,MidEndLast loop-var-in-range-modifiable-in-body4.p4

the output I see is equivalent to the following (see the in-line comments for the things that look like problems to me):

    @name("ingressImpl.n") bit<8> n_0;
    // Note that this i_0 is a _different_ one than i_0 that is
    // the loop variable in the for loop below.
    @name("ingressImpl.i") bit<8> i_0;
    action loopbody1() {
        // Note that this i_0 on the right-hand side is used
        // uninitialized.
        i_0 = i_0 + 8w1;
        n_0 = n_0 + i_0;
        hdr.ethernet.dstAddr[7:0] = hdr.ethernet.dstAddr[7:0] + 8w255;
    }
    apply {
        n_0 = hdr.ethernet.dstAddr[7:0];
        for (@name("ingressImpl.i") bit<8> i_0 in 8w1 .. hdr.ethernet.dstAddr[7:0]) {
            loopbody1();
        }
        hdr.ethernet.srcAddr[7:0] = n_0;
        stdmeta.egress_spec = 9w1;
    }

loop-var-in-range-modifiable-in-body4.p4.txt

[jafingerhut]

@ChrisDodd Food for thought on a subtle point involving for loops over ranges where the loop variable is modifed in the body.

I wouldn't mind if we changed the compiler and/or language spec to restrict programs so that they cannot modify the loop variable in the loop body, at least not for the for (typeRef var in min..max) kinds of loops, and probably also the for (typeRef var in value_list) kind.

I also don't mind if p4c does allow modifying the loop variable in such loops, as long as p4c and the spec agree on what the behavior should be.

2025-Jan-28 update to this comment: My guess is that we could consider the compiler's output correct, if we removed the bit<8> typeRef from the line for (@name("ingressImpl.i") bit<8> i_0 in 8w1 .. hdr.ethernet.dstAddr[7:0]), meaning that i_0 in the loop body was referring to the i_0 declared in the control before the apply {. The main down-side to this approach is that for (var in min..max) is not supported or defined in the language spec, so we would need to extend the language just for the purpose of the intermediate representation of the code (which could be done only for the IR, and not in P4 as defined by the language spec).

[vlstill]

My take on this is:

• I would consider x..y range to be conceptually a function (operator) that takes bounds and returns a range. The for loop then iterates over the range. Therefore, it should behave as such with respect to side effects -- the latter change of x/y in the loop body does not have effect on the range, because the range is already evaluated. We might want to add this to side effect ordering if it is not already there:

  for (T val in x..y) { /* body */ }
  ===>
  /* type */ x_copy = x;
  /* type */ y_copy = y;
  for (T val in x_copy..y_copy) { /* body */ }

• The second component is if the body of the loop can modify the loop variable, or if it is considered constant within the body. This is a bit more tricky in my opinion.

  • For range loop, I can imagine either that it cannot to avoid confusion, or that it can, but it does not affect the iteration (again, iteration is over a range, which is effectively immutable during iteration).
  • For C-style loop, either we forbid it because it is hard to implement/confusing, or we must consider the full complexity of loops that modify iteration variable in multiple places.

  Personally, I would lean towards considering iteration variables constant within loop body, and emitting errors when modification is attempted in either for cycle style.

---

BTW. I find the transformation with the extra action quite peculiar, what is the motivation for that?

[jafingerhut]

BTW. I find the transformation with the extra action quite peculiar, what is the motivation for that?

I am not able to quickly determine which pass does this, but it is reasonably common that assignment statements in a control can be replaced with a "dummy table", i.e. a table with no key fields at all (thus no entries can be added, thus all applies on it will always result in a miss, executing the default_action), one const default_action equal to a new synthesized action, and the assignment statements that were in the control apply body moved into the body of that action.

Historically, I believe this is done for back ends that want everything in the control to look like either a conditional branch, or a table apply, and nothing else.

And BMv2 back end is such a back end.

Note that in my original comment, I did not include the "dummy table" for brevity. I said that the output of the compiler was equivalent to what I wrote, which it is. I just removed the dummy table and invoked the action directly in the body of the control. If you want to see the dummy table in its full glory, just run this command on the source file I provided in the attached zip file of the original comment:

mkdir -p tmp
p4test --dump tmp --top4 FrontEndLast,FrontEndDump,MidEndLast <filename>.p4

then look in the tmp directory for the output files.