Hi everyone,I propose the following changes to the LangRef specification of control flow in regions.Replace "When exiting a Region, control is returned to the enclosing operation." with the following "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to any enclosing op."RationaleIt is unclear what "exiting a region" means in the context of MLIR. (Historical note: one of the early versions of the region specification allowed blocks in regions not to have terminators, which would correspond to "exiting" the region). Regions are CFGs of blocks and the proposed change makes it clear that the CFG property is preserved. The terminator semantics defines whether the control flow remains within the region or is deferred to an enclosing op.MotivationConsider an abstract "structured control flow" dialect that is used to model the equivalent of the "break" statement in C.scf.while(...) {
"some.op"() : () -> ()
scf.if(...) {
scf.break; // this breaks out of the closest surrounding loop
}
"another.op"() : () -> ()
scf.terminator // explicit terminator for clarity
}In order to model the "break", the terminator in a region should be able to transfer the control flow to any ancestor, not just the immediate parent. The immediate parent itself is not being a terminator, its semantics cannot include the forwarding of control flow to its parent when the control flow returned to it by "break".
The proposed formulation also enables the common early-return pattern in function-like operations should they want to support it.ImplicationsThis makes the control flow transfer less across regions. In particular, there is a risk of semantics conflicts regarding the control flow between an operation with regions and terminators used within them. For example, an operation with two regions may have a semantics that both regions are executed in order, but the first region may have a terminator that unconditionally transfers the control flow to a non-immediate ancestor, thus breaking the contract of its immediate parent operation. However, this situation is already possible if the first region in question contains, e.g., a call-like operation to a function that never returns. Therefore, the compatibility of control flow contracts should be left to the semantics of the operation. In the same example, if the operation with two regions wants to guarantee that both regions are executed, it can restrict the set of ops, including terminators, that are allowed in its regions (potentially using trait-based mechanisms). Otherwise, it can ensure only that the second region is executed after the first region reaches its terminator, which it will never do in both cases.If we decide that terminators should be only allowed to transfer the control flow to the immediate parent, I still suggest changing the wording to "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to the immediately enclosing operation".I further propose to remove the phrase "A Region may also enter another region within the enclosing operation." This seems to be an editing artifact. It is unclear how a region can enter another region. With both wordings proposed above, a terminator in the region may transfer the control flow back to the immediately enclosing operation, which in turn may transfer it to another region it encloses. The above explanation can be added instead, if necessary.---- Alex
--
You received this message because you are subscribed to the Google Groups "MLIR" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mlir+uns...@tensorflow.org.
To view this discussion on the web visit https://groups.google.com/a/tensorflow.org/d/msgid/mlir/CAPL655gfd_DHJJ5zKoeP-UyZqat2DqQg4VS%2ByN9gOBGCSoGkEQ%40mail.gmail.com.
Some concrete issues fall out of this "terminator in the middle of a block" view: your `scf.if` can be seen as having no side-effects, the usual rules of sequence of operations in a block allows to reorder "another.op" before the `scf.if` even if "another.op" has a side effect. This would not be valid anymore.
--Mehdi--The proposed formulation also enables the common early-return pattern in function-like operations should they want to support it.ImplicationsThis makes the control flow transfer less across regions. In particular, there is a risk of semantics conflicts regarding the control flow between an operation with regions and terminators used within them. For example, an operation with two regions may have a semantics that both regions are executed in order, but the first region may have a terminator that unconditionally transfers the control flow to a non-immediate ancestor, thus breaking the contract of its immediate parent operation. However, this situation is already possible if the first region in question contains, e.g., a call-like operation to a function that never returns. Therefore, the compatibility of control flow contracts should be left to the semantics of the operation. In the same example, if the operation with two regions wants to guarantee that both regions are executed, it can restrict the set of ops, including terminators, that are allowed in its regions (potentially using trait-based mechanisms). Otherwise, it can ensure only that the second region is executed after the first region reaches its terminator, which it will never do in both cases.If we decide that terminators should be only allowed to transfer the control flow to the immediate parent, I still suggest changing the wording to "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to the immediately enclosing operation".I further propose to remove the phrase "A Region may also enter another region within the enclosing operation." This seems to be an editing artifact. It is unclear how a region can enter another region. With both wordings proposed above, a terminator in the region may transfer the control flow back to the immediately enclosing operation, which in turn may transfer it to another region it encloses. The above explanation can be added instead, if necessary.---- Alex
You received this message because you are subscribed to the Google Groups "MLIR" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mlir+uns...@tensorflow.org.
To view this discussion on the web visit https://groups.google.com/a/tensorflow.org/d/msgid/mlir/CAPL655gfd_DHJJ5zKoeP-UyZqat2DqQg4VS%2ByN9gOBGCSoGkEQ%40mail.gmail.com.
Hi Alex,A few comments here.1) By allowing control to transfer to arbitrary ancestor ops as opposed to just the parent op (which holds the region), you are breaking the notion of a region being similar to a function w.r.t entry/exit. The current region abstraction being similar to a function is also mentioned in the doc: a function execution is actually what you get when one executes the region exactly once, as you know. Depending on other abstractions you'd like to model with a region, you could execute it multiple times based on other things. But the key commonality is that control returns to the enclosing op when you exit the region.
2) I find your other point on the semantics of "exiting a region" being unclear in MLIR to be inaccurate. Exiting a region has always meant control being transferred to the enclosing operation (as you quote further below), from various places in the doc. The documentation could spell it out even more clearly if needed. I can understand though if the confusion just stemmed from confusing std.return with a C function return. Your motivation to model other higher-level structured control flow things as the reason for proposing this change makes sense, but saying that "exiting a region is unclear and hence let's generalize the region control flow exit model" doesn't.
3) While you propose having a way to return control to other ancestor ops from the region, it's not clear if you'd like to accomplish this through new terminator ops with their own special semantics and which could be context sensitive, or by modifying std.return. If it's the latter, that's a big concern as well -- because it's nice to have std.return to just mean (return to parent op of the region top level it appears in.)
4) Even without the generalization you propose, since it would be possible to represent the desired control flow with albeit flatter / lower level (less hierarchy / structure) ops, it isn't clear whether the generalization itself makes it easier for analysis / transformation. Even if it does, should one meddle with the current region notion or introduce a completely new thing for this? It does look like there is benefit in analyses and transforms to have the assurance that the terminator of a block will behave in a well-defined restricted way without having to actually look at each terminator to see if it's doing something crazy/unworkable for that pass.
In summary, while I see the motivation to model certain scf notions, breaking the current region's control flow model looks disruptive to all the things it can already enable -- probably more exploration is needed here. I couldn't immediately understand whether Mehdi's concerns were related to (1) and (4) above or separate.~ Uday
On Friday, December 20, 2019 at 4:19:36 PM UTC+5:30, Alex Zinenko wrote:Hi everyone,I propose the following changes to the LangRef specification of control flow in regions.Replace "When exiting a Region, control is returned to the enclosing operation." with the following "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to any enclosing op."RationaleIt is unclear what "exiting a region" means in the context of MLIR. (Historical note: one of the early versions of the region specification allowed blocks in regions not to have terminators, which would correspond to "exiting" the region). Regions are CFGs of blocks and the proposed change makes it clear that the CFG property is preserved. The terminator semantics defines whether the control flow remains within the region or is deferred to an enclosing op.MotivationConsider an abstract "structured control flow" dialect that is used to model the equivalent of the "break" statement in C.scf.while(...) {
"some.op"() : () -> ()
scf.if(...) {
scf.break; // this breaks out of the closest surrounding loop
}
"another.op"() : () -> ()
scf.terminator // explicit terminator for clarity
}In order to model the "break", the terminator in a region should be able to transfer the control flow to any ancestor, not just the immediate parent. The immediate parent itself is not being a terminator, its semantics cannot include the forwarding of control flow to its parent when the control flow returned to it by "break".The proposed formulation also enables the common early-return pattern in function-like operations should they want to support it.ImplicationsThis makes the control flow transfer less across regions. In particular, there is a risk of semantics conflicts regarding the control flow between an operation with regions and terminators used within them. For example, an operation with two regions may have a semantics that both regions are executed in order, but the first region may have a terminator that unconditionally transfers the control flow to a non-immediate ancestor, thus breaking the contract of its immediate parent operation. However, this situation is already possible if the first region in question contains, e.g., a call-like operation to a function that never returns. Therefore, the compatibility of control flow contracts should be left to the semantics of the operation. In the same example, if the operation with two regions wants to guarantee that both regions are executed, it can restrict the set of ops, including terminators, that are allowed in its regions (potentially using trait-based mechanisms). Otherwise, it can ensure only that the second region is executed after the first region reaches its terminator, which it will never do in both cases.If we decide that terminators should be only allowed to transfer the control flow to the immediate parent, I still suggest changing the wording to "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to the immediately enclosing operation".I further propose to remove the phrase "A Region may also enter another region within the enclosing operation." This seems to be an editing artifact. It is unclear how a region can enter another region. With both wordings proposed above, a terminator in the region may transfer the control flow back to the immediately enclosing operation, which in turn may transfer it to another region it encloses. The above explanation can be added instead, if necessary.---- Alex
--
You received this message because you are subscribed to the Google Groups "MLIR" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mlir+uns...@tensorflow.org.
To view this discussion on the web visit https://groups.google.com/a/tensorflow.org/d/msgid/mlir/87c52a65-a683-4854-814a-51d5921a99b5%40tensorflow.org.
Okay, since people seem to be focused on the motivational example more than on the change itself, let me rephrase.Replace "When exiting a Region, control is returned to the enclosing operation." with the following "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to the immediately enclosing op."This may be followed up with an explanation "The semantics of the enclosing op defines where the control flow is transmitted next. It may, for example, enter a region of the same op, including the same region that returned the control flow. If the enclosing op is a terminator itself, it can transfer the control flow to another block of its region, like any other terminator".RationaleIt is unclear what "exiting a region" means in the context of MLIR. (Historical note: one of the early versions of the region specification allowed blocks in regions not to have terminators, which would correspond to "exiting" the region). Regions are CFGs of blocks and the proposed change makes it clear that the CFG property is preserved. The terminator semantics defines whether the control flow remains within the region or is deferred to an enclosing op.MotivationThe specification does not state unambiguously whether the control flow can be transmitted form a region to the immediately enclosing op only, or to any enclosing op. This leaves room for defining control flow operations that may potentially introduce the equivalent of terminators in the middle of a block, such as attempts to implement "early-return" from a function or "for-if-break" scheme without using custom terminators.I further propose to remove the phrase "A Region may also enter another region within the enclosing operation." This seems to be an editing artifact. It is unclear how a region can enter another region. With both wordings proposed above, a terminator in the region may transfer the control flow back to the immediately enclosing operation, which in turn may transfer it to another region it encloses. The above explanation can be added instead, if necessary.
To view this discussion on the web visit https://groups.google.com/a/tensorflow.org/d/msgid/mlir/CAPL655ja4DvZhWp_Yk7CdTSmOx5FZc-N%3DcLY%2BirpgLzjhSf7GA%40mail.gmail.com.
Okay, since people seem to be focused on the motivational example more than on the change itself, let me rephrase.Replace "When exiting a Region, control is returned to the enclosing operation." with the following "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to the immediately enclosing op."This may be followed up with an explanation "The semantics of the enclosing op defines where the control flow is transmitted next. It may, for example, enter a region of the same op, including the same region that returned the control flow. If the enclosing op is a terminator itself, it can transfer the control flow to another block of its region, like any other terminator".
RationaleIt is unclear what "exiting a region" means in the context of MLIR. (Historical note: one of the early versions of the region specification allowed blocks in regions not to have terminators, which would correspond to "exiting" the region). Regions are CFGs of blocks and the proposed change makes it clear that the CFG property is preserved. The terminator semantics defines whether the control flow remains within the region or is deferred to an enclosing op.MotivationThe specification does not state unambiguously whether the control flow can be transmitted form a region to the immediately enclosing op only, or to any enclosing op. This leaves room for defining control flow operations that may potentially introduce the equivalent of terminators in the middle of a block, such as attempts to implement "early-return" from a function or "for-if-break" scheme without using custom terminators.
To unsubscribe from this group and stop receiving emails from it, send an email to ml...@tensorflow.org.
To view this discussion on the web visit https://groups.google.com/a/tensorflow.org/d/msgid/mlir/87c52a65-a683-4854-814a-51d5921a99b5%40tensorflow.org.
---- Alex---- Alex
Hi Alex,
This looks good to me. Just a couple of comments below.
On Thursday, December 26, 2019 at 7:44:26 PM UTC+5:30, Alex Zinenko wrote:Okay, since people seem to be focused on the motivational example more than on the change itself, let me rephrase.Replace "When exiting a Region, control is returned to the enclosing operation." with the following "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to the immediately enclosing op."This may be followed up with an explanation "The semantics of the enclosing op defines where the control flow is transmitted next. It may, for example, enter a region of the same op, including the same region that returned the control flow. If the enclosing op is a terminator itself, it can transfer the control flow to another block of its region, like any other terminator".I think we can drop the last sentence because that's already clear/implied - there's nothing special there.
RationaleIt is unclear what "exiting a region" means in the context of MLIR. (Historical note: one of the early versions of the region specification allowed blocks in regions not to have terminators, which would correspond to "exiting" the region). Regions are CFGs of blocks and the proposed change makes it clear that the CFG property is preserved. The terminator semantics defines whether the control flow remains within the region or is deferred to an enclosing op.MotivationThe specification does not state unambiguously whether the control flow can be transmitted form a region to the immediately enclosing op only, or to any enclosing op. This leaves room for defining control flow operations that may potentially introduce the equivalent of terminators in the middle of a block, such as attempts to implement "early-return" from a function or "for-if-break" scheme without using custom terminators.Didn't we already state at other places that only terminators can transfer control flow and since terminators can only appear at the end of block, control flow can only be transferred from an end of block? The clarification on "where control flow can be transferred to" doesn't help with "where it can be transferred from". So the latter has to be separately clarified. The change you propose further below sounds good anyway -- I think it was trying to say that an op in a region can itself have a region but the wording wasn't really meaningful.
To unsubscribe from this group and stop receiving emails from it, send an email to mlir+uns...@tensorflow.org.
To view this discussion on the web visit https://groups.google.com/a/tensorflow.org/d/msgid/mlir/f94384aa-c666-403a-8588-f6a4d0584c23%40tensorflow.org.
On Fri, Dec 27, 2019 at 4:05 AM 'Uday Bondhugula' via MLIR <ml...@tensorflow.org> wrote:Hi Alex,This looks good to me. Just a couple of comments below.
On Thursday, December 26, 2019 at 7:44:26 PM UTC+5:30, Alex Zinenko wrote:Okay, since people seem to be focused on the motivational example more than on the change itself, let me rephrase.Replace "When exiting a Region, control is returned to the enclosing operation." with the following "A terminator of a block within a region may transfer the control flow to another block in this region, or return it to the immediately enclosing op."This may be followed up with an explanation "The semantics of the enclosing op defines where the control flow is transmitted next. It may, for example, enter a region of the same op, including the same region that returned the control flow. If the enclosing op is a terminator itself, it can transfer the control flow to another block of its region, like any other terminator".I think we can drop the last sentence because that's already clear/implied - there's nothing special there.Works for me.Should we explicitly clarify that terminators are allowed to have regions though?
RationaleIt is unclear what "exiting a region" means in the context of MLIR. (Historical note: one of the early versions of the region specification allowed blocks in regions not to have terminators, which would correspond to "exiting" the region). Regions are CFGs of blocks and the proposed change makes it clear that the CFG property is preserved. The terminator semantics defines whether the control flow remains within the region or is deferred to an enclosing op.MotivationThe specification does not state unambiguously whether the control flow can be transmitted form a region to the immediately enclosing op only, or to any enclosing op. This leaves room for defining control flow operations that may potentially introduce the equivalent of terminators in the middle of a block, such as attempts to implement "early-return" from a function or "for-if-break" scheme without using custom terminators.Didn't we already state at other places that only terminators can transfer control flow and since terminators can only appear at the end of block, control flow can only be transferred from an end of block? The clarification on "where control flow can be transferred to" doesn't help with "where it can be transferred from". So the latter has to be separately clarified. The change you propose further below sounds good anyway -- I think it was trying to say that an op in a region can itself have a region but the wording wasn't really meaningful.Good point, I checked and we currently say "A block is a sequential list of operations without control flow (calls are not considered control flow for this purpose)", which isn't exactly true since operations in the block can transfer the control flow to their regions or even to "closure" regions defined elsewhere, such as function bodies. Should we also rephrase the text in parentheses as "(entering regions is not considered control flow for this purpose)" ? We cannot state the control flow merges or always returns to the op that transferred it to the region since it may be never transferred back, which we explicitly allow.
To view this discussion on the web visit https://groups.google.com/a/tensorflow.org/d/msgid/mlir/f94384aa-c666-403a-8588-f6a4d0584c23%40tensorflow.org.
---- Alex