Another Compaction Bug (Sorry)

[calebmkim]

I just realized my fix for #1852 still leaves another bug.

Suppose we have a component foo that is @promotable

component foo (@promotable(4) @go go, ...) -> (...)

If we compact the following seq

@promotable(5) seq {
  @promotable(4) invoke foo()().
  @promotable(1) write_to_reg;
}

this means that we need foo to be static, since compaction involves taking @promotable -> static<n> control. (Also, any components that foo instantiates now also need to be promoted to static).
However, the decision to make foo--or any other component--static doesn't happen until the static-promotion pass, which runs after compaction. There's nothing in the promotion pass that forces foo to be static.

Solution/Future Direction

1. One solution could be to merge compaction and promotion passes, since they are philisophically doing the same thing (converting dynamic code to static code). One reason why I don't think this is actually too bad is that most of the analysis in the compaction pass is externalized to analyses. In fact, if you look at the code of the finish_seq function for both compaction and promotion, there are actually some similarities: they basically iterate thru the existing seq, but the actual conversion of the seq to static control is outsourced to a separate function.

2. Another solution is, in the compaction pass, to keep a list of all the components we have committed to promotion (i.e., all the components whose go port was written to in a seq that we compacted). At the end, we attach an attribute to all the components that must be static, and the promotion pass must promote them. This will lead to more aggressive promotion than before.

I'm still not 100% sure which solution is better, so I'd be happy to hear other people's thoughts.

Either way, there’s still the overall question of how to apply the promotion heuristics. I propose that, long-term, there should be some sort of universal promotion heuristic that applies to both compaction and promotion, while in the short term, we apply compaction aggressively (that is what we are doing currently), while performing generic promotion based on the heuristics.

[rachitnigam]

I think a similar problem came up during our synchronous meeting. One of the things I said is that promotion decisions need to be committed before they are allowed to influence other components so maybe that is a possible solution? I think merging is not a very scalable solution if we want other passes to exist in the pipeline between static inference and promotion.

[calebmkim]

Yeah, I remember going over a similar problem (sorry, I forgot about this detail when implemented things). I don't love the idea of merging compaction and promotion, but I'll try to explain why I can't think of any good alternatives.

Currently the order of passes is: inference->compaction->promotion.

One of the things I said is that promotion decisions need to be committed before they are allowed to influence other components so maybe that is a possible solution?

For inference, I don't think this principle is necessary. In other words, if foo instantiates bar, I don't think we need to make a decision on whether to promote bar when we are inferring foo's control. If static-promotion ends up not promoting bar, the pass is smart enough to remove and then try to re-infer the @promotable annotation (where necessary) from foo's groups/control. All of this is externalized in InferenceAnalysis, so if we want to add passes in between inference and promotion, these passes can use InferenceAnalysis to perform the same fix-up that static-promotion does. Furthermore, following this principle would require merging inference and promotion, which leads to its own set of problem.

For compaction, I agree with this principle. In other words, we need to be committed to a decision on whether to promote bar at the time we are trying to compact foo's control. The problem is, I don't see a way to do this without merging promotion and compaction. Here's why:

If we want to be committed to a promotion decision for bar when we are trying to compact foo, it seems like there are two broad paths we can take:

1. Promotion and Compaction occur in the same pass, and we do post-order traversal.
2. Promotion runs before compaction.

(Compaction before promotion can't work if we want to follow this principle, since we don't know if we are promoting bar at the time we are trying to compact foo).

The problem with Promotion before Compaction

It's basically this issue: #1852. Basically, when we compact bar, we change its timing behavior: this change "propagates", meaning we also have to change foo's timing behavior as well.
I can explain more in-depth why I don't think it's workable to have a fixup for this, but the tl;dr is that performing a fix-up (similar to InferencAnalysis) isn't always possible on static<n> control, since we have to come up with timing behaviors. InferenceAnalysis is always free to remove a @promotable attribute when it can no longer infer things.

Another note: solution (2) in the original comment might work, but it doesn't follow this principle. It makes compaction decisions dictate promotion decisions rather than the other way around (i.e., if we make the decision to compact foo's control, then it requires us to promote bar. Whereas the "better" solution seems to be: if we promote bar, then the option to compact foo's control is available to us if we want).

[calebmkim]

After a synchronous discussion last Thursday, we couldn't really come up with any other solution besides merging the passes. (The reason(s) are outlined in the above comment)

We agreed to the following plan: try to externalize compaction into an analysis, and merge compaction and promotion. This way, if we decide that the passes are better separate, hopefully it will be less effort to merge them.

[rachitnigam]

Okay, sounds good! Thanks for thinking about this. I think a good litmus test for this merge is figuring out another pass that needs to live between inference and promotion (i.e. one that relies on control programs that can be rescheduled) and seeing what kind of interface it needs to use.

[calebmkim]

Yeah, so if I imagine an imaginary pass that lives between inference and promotion, here's what it would have to do.

tl;dr it will have to call InferenceAnalysis.fixup_timing a bunch of times, and adjust the signature of the component in the Visitor's finish method.

In more detail:

It will probably require an InferenceAnalysis field, like the static-promotion pass has.

It will have to call inference_analysis.fixup_{ctrl}, each time it visits a ctrl statement, like so.

Also, it will have to have a finish method that cleans up the changes we made for the component. It will be similar to what static-promotion does. inference_analysis again makes it pretty easy. The biggest thing will be calling inference_analysis.adjust_component to account for the new timing information. You also will have to re-annotate the @go ports of the component (maybe there should be a method in InferenceAnalysis that does this).

Finally, the start function will have to call fixup_timing as well, to account for other component's whose signature has changed.

Not perfect but overall pretty low effort?

[rachitnigam]

Interesting! I wonder if this pattern can be abstracted into a little trait that overrides the visitor methods and does this fixup for the pass.

Then, instead of implementing Visitor, a user could implement that trait and rely on the overridden methods to do the right thing.

[calebmkim]

Yeah, I think this makes sense to me. One question about what you had in mind (correct me if any of my assumptions are wrong):

It seems like we want to be able to provide whoever is writing the pass with all of the familiar functions, like start_seq, finish_seq, enable, etc. However, right before start_seq, finish_seq, etc. is run, we want to run fixup-timing right before it (We should also run fixup-timing right before and right after each time we visit the component's control).
This makes it seem like there would be a some repeated code between the Visitor Trait, and this new trait, which is fine?

[rachitnigam]

Yeah, I think there would need to be some repeated behavior between the two implementation. Ideally, we can override the top-level function responsible for dispatching to the start_* or finish_* functions but I haven't thought very carefully about whether that would be clean/possible