Proposed changes to Region Control Flow in LangRef

[Alex Zinenko]

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."

Rationale

It 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.

Motivation

Consider 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.

Implications

This 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

[Mehdi AMINI]

On Fri, Dec 20, 2019 at 2:49 AM 'Alex Zinenko' via MLIR <ml...@tensorflow.org> 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."

Rationale

It 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.

Motivation

Consider 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".

I am concerned about this: it seem equivalent to allowing terminator in the middle of a block. Here you could make the scf.if() a terminator with a single successor to the "another.op":

scf.while(...) {

  "some.op"() : () -> ()

  scf.if(...) [^continuation] {

    scf.break; // this breaks out of the closest surrounding loop

  }

^continuation:

  "another.op"() : () -> ()

  scf.terminator // explicit terminator for clarity

}

 

This would work with the current rule assuming a semantic where the terminator can either exit the region or continue to a successor.

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.

Implications

This 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.

[Uday Bondhugula]

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

[Alex Zinenko]

This may require differentiating between a "breakable if", which is a terminator and a plain "if", which is not. AFAIK, we don't have conditional terminators and introducing them would be another can of worms. Let's explore this separately. My main goal here is to remove the handwavy text from LangRef.

 

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.

I understand the concern of having a pseudo-terminator in the middle of a block. It's not clear to me that we can say it has no side effects (the "if" operation itself may not, but its body may have them). This does not decrease the validity of your concern though.

 

-- 

Mehdi

The proposed formulation also enables the common early-return pattern in function-like operations should they want to support it.

Implications

This 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.

--

-- Alex

[Alex Zinenko]

On Sat, Dec 21, 2019 at 12:02 PM 'Uday Bondhugula' via MLIR <ml...@tensorflow.org> wrote:

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.

The analogy with function is yet another artifact of the iteration on the proposal that I considered removing. The two mentions of "function" in region definition are essentially examples (" function body is an example of a region", "behavior is similar to that of a function body"), they are not meant to define what the region is. Quite the inverse, functions should be defined in terms of regions. I decided against removing these mentions because they seem like useful examples. The first mention is a straightforward illustration. But if they are confusing, they should be phrased more carefully. 

Executing a region once is not sufficient for it to be function body-like, there are more conditions on it, including the absence of implicit capture (aka "isolated from above" trait).

 

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. 

If "exiting a region" means "control being transferred to the enclosing operation", then the phrase "When exiting a Region, control is returned to the enclosing operation" means "when transferring control to the enclosing operation, control is returned to the enclosing operation". This is a tautology and should be removed altogether.

 

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.)

I don't think std.return is anyhow special. It's a terminator. The semantics of it may involve transferring the control to another block, or to an ancestor, just like any other terminator. As such, the semantics of std.return is out of scope here.

 

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.

It can also be represented with CFG only, the question is not necessarily the representational power. I think this is similar to what Mehdi mentioned and there are indeed non-trivial interaction of different control flow bits.

 

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."

Rationale

It 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.

Motivation

Consider 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.

Implications

This 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.

--

-- Alex

[Alex Zinenko]

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".

Rationale

It 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.

Motivation

The 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.

--

-- Alex

[Mehdi AMINI]

On Thu, Dec 26, 2019 at 6:14 AM 'Alex Zinenko' via MLIR <ml...@tensorflow.org> 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".

Rationale

It 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.

Motivation

The 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.

Seems fine to me!

-- 

Mehdi

 

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.

[Uday Bondhugula]

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.

 

Rationale

It 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.

Motivation

The 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. 

~ Uday

 

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

[Alex Zinenko]

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?

 

 

Rationale

It 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.

Motivation

The 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 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.

--

-- Alex

[Uday Bondhugula]

On Friday, December 27, 2019 at 5:54:20 PM UTC+5:30, Alex Zinenko wrote:

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?

Sure, sounds good!

 

 

 

Rationale

It 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.

Motivation

The 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.

That's right - what you propose sounds good and is actually needed. Rephrasing to "A block is a sequential list of operations without control flow (a call or entering an op's region is not considered control flow for this purpose)" sounds better? This should make it clear since for the 'call' part, it's just the standard basic block /  LLVM model. 

~ Uday

 

 

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