This is an archive of the discontinued LLVM Phabricator instance.

[mlir][SCCP] Add support for propagating constants across inter-region control flow
ClosedPublic

Authored by rriddle on Apr 18 2020, 11:08 PM.

Details

Summary

This is possible by adding two new ControlFlowInterface additions:

  • A new interface, RegionBranchOpInterface

This interface allows for region holding operations to describe how control flows between regions. This interface initially contains two methods:

  • getSuccessorEntryOperands

Returns the operands of this operation used as the entry arguments when entering the region at index, which was specified as a successor by getSuccessorRegions. when entering. These operands should correspond 1-1 with the successor inputs specified in getSuccessorRegions, and may be a subset of the entry arguments for that region.

  • getSuccessorRegions

Returns the viable successors of a region, or the possible successor when branching from the parent op. This allows for describing which regions may be executed when entering an operation, and which regions are executed after having executed another region of the parent op. For example, a structured loop operation may always enter into the loop body region. The loop body region may branch back to itself, or exit to the operation.

  • A trait, ReturnLike

This trait signals that a terminator exits a region and forwards all of its operands as "exiting" values.

These additions allow for performing more general dataflow analysis in the presence of region holding operations.

Depends On D78397

Event Timeline

rriddle created this revision.Apr 18 2020, 11:08 PM

It's fantastic to have the same conditional constant propagation work for higher-order control flow ops and across nested regions! I think the revision title should be updated to better reflect that. "Region-based control flow" doesn't immediately imply that this works across nested regions / in and out of regions and not for just intra-region.

mlir/include/mlir/Interfaces/ControlFlowInterfaces.h
94–99

ReturnLike trait ops should also produce zero results I believe - but its results are probably harmless / have no meaning since blocks with ReturnLike terminators won't properly dominate anything and so those results would be unused anyway. We aren't doing a zero result trait check on IsTerminator as well, but they are I guess allowed to have results (a way to send values to all successors for say branch like operations).

rriddle updated this revision to Diff 258623.Apr 19 2020, 1:26 PM

Resolve comments

bondhugula requested changes to this revision.Apr 19 2020, 2:46 PM

may be executed when entering an operation, and which regions are executed by "branching" from other regions

This could be confusing since one can't directly branch from another region (as in using a 'br'). Change "by branching from other regions" to "after having executed another region of the parent op". Also, this commit summary has more information than the ODS description of getSuccessorRegions in some ways. Consider making the ODS doc desc. more comprehensive.

The operands may correspond to a subset of the entry arguments to the region.

I think you meant the other way? The entry arguments to the region may correspond to a subset of the operands.

mlir/include/mlir/Interfaces/ControlFlowInterfaces.h
93–94

Is this the right file to put this trait? Ops that don't implement the op interface above should have access to this trait? (Plus, see the comment on ReturnOp below.)

mlir/lib/Transforms/SCCP.cpp
525–527

You missed marking ReturnOp ReturnLike. As such, you will return early here and miss propagating lattice states to successor regions. Although there is no registered op that will exercise this, this could happen let's say in a special func-like op that has two regions (sort of two functions) and the semantics of the op were to execute the two regions one after the other.

This revision now requires changes to proceed.Apr 19 2020, 2:46 PM
rriddle updated this revision to Diff 258634.Apr 19 2020, 6:31 PM
rriddle marked 5 inline comments as done.

Resolve comments

may be executed when entering an operation, and which regions are executed by "branching" from other regions

This could be confusing since one can't directly branch from another region (as in using a 'br'). Change "by branching from other regions" to "after having executed another region of the parent op". Also, this commit summary has more information than the ODS description of getSuccessorRegions in some ways. Consider making the ODS doc desc. more comprehensive.

The operands may correspond to a subset of the entry arguments to the region.

I think you meant the other way? The entry arguments to the region may correspond to a subset of the operands.

No, I mean the operands returned by this method may correspond to a subset of the entry arguments. This method shouldn't return more operands than there are entry block arguments.

mlir/include/mlir/Interfaces/ControlFlowInterfaces.h
93–94

Yes this is the right place. OpDefinition.h is not the right place to put every possible trait, and is something that I've been purposely moving away from. It is better to keep the interfaces and traits that pertain to a specific abstraction in one place, e.g., the traits *and* interfaces for side effect modeling are in SideEffects.h. Realistically the files in this directory should remove the redundant "Interfaces" from the end of the name.

mlir/lib/Transforms/SCCP.cpp
525–527

Such an op isn't possible ATM given the constraints of ReturnOp. I intend to add interprocedural support here, at which point having it on ReturnOp would be useful. Also as a policy I like to avoid trying to mark every possible op that could take advantage of something. IMO it is better to separate adding a feature, and using it in every possible place. It keeps this patch more focused.

rriddle marked an inline comment as done.Apr 19 2020, 7:10 PM
rriddle added inline comments.
mlir/lib/Transforms/SCCP.cpp
525–527

To clarify, I do intend to add this trait/interface to the things that can use it in a followup.

may be executed when entering an operation, and which regions are executed by "branching" from other regions

This could be confusing since one can't directly branch from another region (as in using a 'br'). Change "by branching from other regions" to "after having executed another region of the parent op". Also, this commit summary has more information than the ODS description of getSuccessorRegions in some ways. Consider making the ODS doc desc. more comprehensive.

The operands may correspond to a subset of the entry arguments to the region.

I think you meant the other way? The entry arguments to the region may correspond to a subset of the operands.

No, I mean the operands returned by this method may correspond to a subset of the entry arguments. This method shouldn't return more operands than there are entry block arguments.

Oh, I was confused thinking about the parent op's operands. Consider changing:
"The operands may correspond to a subset of the entry arguments to the region." -> ".... entry arguments of the containing region"

mlir/include/mlir/Dialect/LoopOps/LoopOps.td
179

I think this should be called getSuccessorRegionEntryOperands or getSuccRegionEntryOperands.

179

Since this op has exactly one region and so index can only be zero, update the doc comment to reflect that.

mlir/include/mlir/Interfaces/ControlFlowInterfaces.h
74

Region *region or else it gives the impression that this is a successor to that successor region.

75

successorInputs -> inputs likewise. This is already a RegionSuccessor class.

mlir/include/mlir/Interfaces/ControlFlowInterfaces.td
105

Spell out "used" here, i.e., "used as arguments" or "used as the entry block arguments".

107

typo: specified

121

Nit: that either correspond

mlir/lib/Dialect/LoopOps/LoopOps.cpp
343

index.hasValue() to avoid confusion. What if index has a value and is zero? I can't recall.

mlir/lib/Transforms/SCCP.cpp
525–527

It's just weird that the standard ReturnOp isn't marked ReturnLike. You could add the support to exploit it later, but no harm marking the more prevalent / core one? Yes, there isn't a need to add it in every other possible place now. OTOH, if ReturnLike doesn't work well for the ReturnOp and you need another trait, then this one should be renamed YieldLike and ReturnLike could be used for ReturnOp and for other declarative ops.

rriddle updated this revision to Diff 258788.Apr 20 2020, 10:28 AM
rriddle marked 10 inline comments as done.

Resolve comments

rriddle retitled this revision from [mlir][SCCP] Add support for propagating constants in the presence of region based control flow. to [mlir][SCCP] Add support for propagating constants across inter-region control flow.Apr 20 2020, 10:28 AM
rriddle edited the summary of this revision. (Show Details)

Thanks for the review Uday! I appreciate the attention to detail.

mlir/lib/Transforms/SCCP.cpp
525–527

Agreed, went ahead and added it. Thanks.

bondhugula requested changes to this revision.Apr 20 2020, 11:02 AM
bondhugula added inline comments.
mlir/lib/Dialect/LoopOps/LoopOps.cpp
357

What if there is no else block here? (empty else region)

362

Likewise, what if the else region has no blocks?

mlir/test/Transforms/sccp-structured.mlir
133

Every loop.if that you have in the test cases has an else. Add one or more without an else block?

This revision now requires changes to proceed.Apr 20 2020, 11:02 AM
bondhugula accepted this revision.Apr 20 2020, 11:27 AM
bondhugula marked an inline comment as done.
bondhugula added inline comments.
mlir/lib/Transforms/SCCP.cpp
141

.. if they are in executable blocks.

472

I think this path is never tested.

mlir/test/Transforms/sccp-structured.mlir
133

Just realized that no values would be yielded without the else. And you are testing for empty regions at one place.

This revision is now accepted and ready to land.Apr 20 2020, 11:27 AM
rriddle marked 4 inline comments as done.Apr 20 2020, 11:28 AM
rriddle added inline comments.
mlir/lib/Dialect/LoopOps/LoopOps.cpp
357

I was originally undecided on how we should treat empty regions. For now, updated to disallow using empty regions as successors.

mlir/test/Transforms/sccp-structured.mlir
133

Do you have a suggestion on what you have in mind? An IfOp can only produce results if it has both a then and an else region. Given that IfOp is implicit capture, nothing would really be testing the structure of the IfOp that isn't tested elsewhere.

rriddle marked 3 inline comments as done.Apr 20 2020, 11:30 AM
rriddle added inline comments.
mlir/test/Transforms/sccp-structured.mlir
133

Seems we crossed comments. Should no longer be necessary if we restrict that successors are non-empty.

rriddle updated this revision to Diff 258802.Apr 20 2020, 11:32 AM

Resolve comments

bondhugula accepted this revision.Apr 20 2020, 12:04 PM
bondhugula added inline comments.
mlir/test/Transforms/sccp-structured.mlir
133

Yes, nothing else to do on this for now.

This revision was automatically updated to reflect the committed changes.