[Semantics] with groups and if/while

[EclecticGriffin]

Making this an issue instead of a discussion to avoid discussion blindness, but we can move that if preferred. This is based on a conversation @sampsyo and I had today.

My current understanding of the semantics for with groups is that they are always active during the execution of the body. We could make this choice for the purpose of an adversarial overlap analysis to avoid possible group conflicts, however, this doesn't make a whole lot of sense given that a with statement is necessarily a combinational group and so can only really be evaluated at the top of the group.

The condition of the loop is generally stable-ish in these contexts, i.e. a combinational component immediately driven by stable inputs, and the actual value (not necessarily the value output by the comb group) used to branch must be stable during the execution of the loop/conditional body. One argument for keeping the with assignments active during the body execution is that the condition of the body that is often realized by a register could be replaced with the conditional guard itself, however we cannot take this as the "true" semantics of while/if because this could cause the body to exit prematurely.

while x < 5 {
   x++;
   // do some stuff
   // other stuff
   // you guessed it, more stuff
}

the above would skip the actual work on the last cycle. It is also easy enough to construct examples that would prematurely exit an if block or (depending on compilation) to switch from the true to false branch mid way through execution.

So clearly the condition computed by the comb group needn't be stable/unchanging during the body execution---otherwise the while loop would not be able to update their counters/conditions during their execution---but if the compiler can prove or otherwise convince itself that the condition is stable after a point it may be computed early and stored in a register to provide a stable condition.

All this suggests that the semantics of a while loop should be that the condition is computed in the "instant" between the conclusion of the body and the start of the next loop (or exit) and that methods of computing the condition early are optimizations to avoid an extra cycle.

If that is the agreed upon semantics, then it does not seem that there is a clear reason to mandate that the with assignments be active during the body evaluation.

@sampsyo please chime in if I missed anything!

[sampsyo]

Awesome; thanks for writing this up! Just a teensy bit of pedantry:

My current understanding of the semantics for with groups is that they are always active during the execution of the body.

To be clear, our compiler doesn't compile things this way—it just semantically reserves the right to do so. So, semantically, a with group "might" be active at any time during the execution of the while/if body, meaning that it can race with reads/writes anywhere in the body. This came up most recently in #1633 (comment), which has a concrete example of an error message we emit.

One argument for keeping the with assignments active during the body execution is that the condition of the body that is often realized by a register could be replaced with the conditional guard itself, however we cannot take this as the "true" semantics of while/if because this could cause the body to exit prematurely.

To put it just slightly differently, the main reason we can think of for the current policy ("with groups might be evaluated at any time during, or continuously throughout, the body") is to allow this "guard the whole body with the condition" compilation style that we don't currently do anyway. But that would clearly mean that while loops must only update their condition as their very last action. This seems overly restrictive. (And even ignoring that hypothetical compilation strategy, the semantic policy by itself seems to impose the same restriction.)

All this suggests that the semantics of a while loop should be that the condition is computed in the "instant" between the conclusion of the body and the start of the next loop (or exit) and that methods of computing the condition early are optimizations to avoid an extra cycle.

This seems like a good direction to me. It is similar to (but cleaner than) option 1 in #1438 (comment). Basically, our policy needs two parts:

• What Calyx gives to the programmer: In while/with loops, the with group is evaluated in the environment just before the body would start executing (and after the previous iteration, if any, finished).
• What Calyx asks from the programmer: This is where I'm a little more stuck. It seems like we might (not sure) need to restrict this somehow to allow for optimization.

Consider this program (based on #1633):

component whatever() -> () {
  cells {
    lt = std_lt(1);
  }

  wires {
    comb group cg {
      lt.left = 1'd0;
      lt.right = 1'd1;
    }

    group g {
      lt.left = 1'd1;
      lt.right = 1'd1;
      // more stuff here to make the group take 1 cycle
    }
  }

  control {
    while lt.out with cg {
      g;
    }
  }
}

The idea in this example is that cg is using an lt comparator, but the body also tries to use the same comparator (combinationally). If we compile this in the current way (the condition gets "registered", and cg gets to go in its own cycle), then we're all good. But if we wanted to evaluate the condition in parallel with the first cycle of the body (as we do in static while loops), we'd have a problem. This seems to imply that, if we want that optimization, there has to be some restriction on what the with group is allowed to do—just saying the with group gets evaluated in isolation (free of interference from anything in the body) doesn't quite seem to cut it.

So I guess my remaining questions are:

1. Do we want to enable that optimization?
2. If so, what restrictions do we need to put on while/if conditions and their comb groups to make that optimization legal? The current ones are probably not right.

[sampsyo]

I feel like I may be going around in circles a bit, but this was oversimplified somewhat:

But if we wanted to evaluate the condition in parallel with the first cycle of the body (as we do in static while loops), we'd have a problem.

This imaginary optimization is quite a bit more complicated than I made it sound for dynamic whiles, I think. You would have to come up with a creative way to avoid letting the "top" of the body have any side effects when the condition is false. This is hard to do while still allowing the body to eventually affect the loop condition.

With that complexity in mind, one could argue reasonably that:

• We never want to do this imaginary optimization…
• …so dynamic whiles should always use our current compilation strategy, i.e., "registering" the with group and executing it alone, in its own cycle…
• …so the semantics should guarantee that isolation, and no extra conditions are necessary.

However, I think that argument is incompatible with the goal of letting while promote automatically to static while, which definitely does want to use that one-cycle-saving optimization. So I think we still need a restriction here: one that requires conditions to be "stable enough," and I'm still not sure how to crystallize that restriction. Ideas welcome…

[rachitnigam]

I'm going to centralize the conversation about this topic to this issue. First off, some context:

• Port-validity as a first class concept #588 : Attempted to highlight the problems with the absence of validity of values as a problem in the semantics.
• Well-formedness of `done` signals #788 : A related but separate problem with the stability condition of done signals of groups. At first blush, I think anything we propose for "control ports" will apply to these as well.
• The `with` operator #934 : Proposed a generalized with operator which activates assignments in a particular scope.

Next, a summary from the synchronous discussion: The core problem that we were trying to solve with comb group and with (#207) was a precise way to describe the kinds of ports that could appear in the conditional position of if and while. The constraints of what is allowed is derived from how compilation works (and probably needs to work for any digital circuit esque target) where the signal is used to implement transitions between FSM states. The simple constraint is that there cannot be any combinational loops between the assignments for computing the condition and the FSM transition and that the value of the conditional port remains the same during the transition (hence the misnomer "stable").
This constraint applies to all "control ports" which are ports used places like done conditions and conditional positions.

Next up, we wanted the ability to have "zero-cycle transitions" when we had a lot of nested if-with and while-with statements:

if a with c1 {
  if b with c2 { ... }
}

This lead to the requirement that conflicts can occur anywhere in the scope of the if or while. However, this decision is separate from the one made when thinking about "stability".

Given this context, we had two desiderata:

1. A "sane" sequential semantics where the conflicts from with are local and easier to think about.
2. The ability to use "obviously stable" operation like a counter or a lt connected to a register (@sampsyo).

Note that these two correspond to the two different problems with with operators.

[sampsyo]

Awesome; thanks for the summary, @rachitnigam. Here is a bit more summary from the synchronous discussion, leading up to a concrete proposal to consider.

The Performance Cost of with

Aside from all the semantic confusion, one big problem with the status quo is that using with basically forces you into wasting a cycle unnecessarily. Consider a typical for-like loop:

for ctr in 0..10 {
  foo();
}

In current Calyx, the existence of with would tempt you into writing something like this:

cells {
  ctr = std_reg(32);
  lt = std_lt(32);
  add = std_add(32);
}
wires {
  comb group cond {
    lt.left = ctr.out;
    lt.right = 32'd10;
  }
  group incr {
    add.left = ctr.out;
    add.right = 32'd1;
    ctr.in = add.out;
    ctr.write_en = 1'd1;
    incr[done] = ctr.done;
  }
}
control {
  while lt.out with cond {
    seq {
      invoke foo();
      incr;
    }
  }
}

That is, you enable a group incr inside the while body to do the increment, and you use a combinational group cond to compare it to a constant. Unfortunately, our current compilation strategy turns all combinational groups into sequential groups by adding a register. So you eventually get something that looks impressionistically like this:

while lt_reg.out {
  seq {
    invoke foo();
    incr;
    cond_seq;
  }
}

Where cond_seq is a brand-new group that works like the old cond but puts its output into a new register, lt_reg. This is pretty disappointing because cond_seq is taking an entire clock cycle to do very little work. So our style of with-based loop came with an annoying hidden cost that no one doing low-level hardware design would opt into if they didn't have to.

That, of course, is just our current compilation strategy. Much of the discussion around with has asked whether it's possible to do a better job: for example, to overlap the computation of cond with the control logic for the loop so it doesn't actually occupy a whole cycle by itself. The big question is whether a hypothetical optimization like this could be made correct, for some reasonable rigorization of what with means. Unfortunately, I think the answer appears to be "no"; we have not yet come up with a good with semantics that would allow this.

Removing with Altogether

One of the options on the table is to stop having with, which makes sense in part because it seems to come with this hidden performance cost. To implement for-like loops in with-free Calyx, you could of course just generate the same code seen above.

In terms of semantics, this sidesteps all the problems we're discussing in this thread. In terms of performance, it's at least no worse, and it is probably better because it's more transparent: that is, the programmer can more easily see the cost. So after this morning's meeting, I am pretty much convinced this makes sense and that we should get rid of with.

Options for Doing Better

It makes sense to ask how, in a future version of Calyx without with, you would write code that doesn’t waste that cycle. We’ll talk about two options here; recall that both are supposed to be better than the status quo.

One option is like this:

while lt_reg.out {
  seq {
    invoke foo();
    par { incr; cond_seq; };
  }
}

That is, you can do both the increment and the condition check in parallel at the end of the loop. This requires a suitable cond_seq that doesn't race with incr, so it's not something the compiler really want to do automatically. It would be the responsibility of the frontend/programmer to carefully think through how to set up cond_seq so it doesn't waste a cycle. This is a bit of an onus to put on the frontend but it’s not too bad.

A second option is to try to put the lt comparison after the end-of-body cycle boundary instead of before it. This option ends up looking more similar to our original code:

wires {
  lt.left = ctr.out;
  lt.right = 32'd10;
}
control {
  while lt.out {
    seq {
      invoke foo();
      incr;
    }
  }
}

That is, we basically take the combinational group from the original version and make them into continuous assignments. This is kinda bad because it uses continuous assignments, but it is a legitimate alternative design point you might want and it takes the same number of cycles as the other option.

On Stability Requirements

Option 1 from the previous section uses a register’s output port for the while condition; Option 2 does not (it uses a comparator permanently attached to a register). A question arises: which ports exactly is safe to use in a condition like that?

It seems to me like both examples above are probably perfectly safe. The reason has to do with the way FSM construction works, which @rachitnigam has addressed above. More importantly than these two specific examples, however, is defining a rule that enforces safety. Options include:

• Requiring every while (and if) condition to be <reg>.out for some register. (Supports Option 1 above but not Option 2.)
• Some generalization of this that allows <reg>.out to pass through some combinational logic first. (Supports both options above.)

Of course, the first policy is easy to state; the second policy is aspirational (we would need to figure out what a policy would actually consist of). We have some ideas for what that policy might look like, but I'll refrain from expanding on that now (maybe in a future post??) to focus instead on keeping things actionable.

Recommendation

At least as a strawman suggestion, we could do these things:

• Remove with from both if and while.
• Require all frontends to adapt, i.e., wherever they were using with, to put their conditions into registers themselves.
• Require all if/while conditions to be <reg>.out for now.
• Tell ourselves that we will think carefully about how to relax that restriction, and allow Option 2, in the future.

I think this plan makes sense if we think the following two things are true:

• Our eventual relaxed policy will not involve reintroducing with, rendering all this thrashing wasted work. (I'm pretty sure this one is true!)
• Changing all the frontends to stop using with won't be too too hard (although of course it will be an annoying amount of engineering). (I think this is likely true as well.)

Maybe that is a proposal we can debate & decide whether to ratify in the short term?

[calebmkim]

I've missed the synchronous discussion for this, but I just want to make sure I'm understanding what the current situation is, especially reading #1732.

Goals

It seems that, we have two eventual goals:

1. Get rid of with on if/while ports
2. Support passing <reg>.out through combinational logic before evaluating the if/while port conditions (e.g., like in Stability check is too strict #1732)

Implications of these goals

In order to support 2, it seems like the only place where this combinational logic (i.e., the logic that <reg>.out is passing through in (2) ) can live is in continuous assignments. In other words, if we want to support if lt.out as a valid port condition, then it seems like lt.left and lt.right must be triggered in continuous assignments (since we're getting rid of with, they can't live in comb groups anymore).

In this case, it seems like we should probably be looking for some sort of requirement on the continuous assignments that trigger if lt.out. I think some sort of recursive requirement would make sense here:

A port is stable iff:

1. It is <reg>.out
2. It is <comb>.out and all of <comb>'s input ports are unconditionally triggered by stable ports in the continuous assignments of the component.

The possible bugs that we've been able to think of (e.g., in #1438) involve the fact that the continuous assignments are not being unconditionally assigned to, and something like the above^ requirements would make them safe from that.

[sampsyo]

In order to support 2, it seems like the only place where this combinational logic (i.e., the logic that <reg>.out is passing through in (2) ) can live is in continuous assignments.

Yep, I think that is exactly right! FWIW, I think that is the Faustian element of this deal: if we decide we don't like with comb groups, then the only alternative is continuous assignments, which are semantically dubious in themselves. At least it sidesteps the weird questions about exactly when the with group is active (continuous assignments are just active all the time!).

I would love to hear more opinions about whether people like this particular trade-off.

In this case, it seems like we should probably be looking for some sort of requirement on the continuous assignments that trigger if lt.out.

Yes, exactly. Your stability requirements definitely seem sufficient and they are simple rules to follow, so that's great. It may be possible to have "tighter" requirements (i.e., to allow some conditional assignments), but it's not clear if we need that relaxation.