Updated error handling to propagate errors upwards in order to signal pass failures.

Addressed reviewer comments and enhanced error handling.

Addressed reviewer comments and added support for failing interface functions.

Added new buildClone operation to the newly introduced AllocationOpInterface.
Made Op interface methods static.
Added support for automatic building of "compatible" deallocation/clone operations based on inverse alias information.
Added support for building "default" DeallocOp/CloneOp values in the case of unknown value sources (e.g. function parameters).
Refined verification part to work on logical result values.

Addressed reviewer comments from @rriddle.

Changed namespace qualifiers to explicitly reference the llvm/mlir namespaces.

@herhut I think it might be beneficial to either remove the ReturnLike trait or to change it in a way such that it automatically provides a "default implementation" of the newly added RegionBranchTerminatorOpInterface.

Adatped ForwardDataFlowSolver to support the newly added RegionBranchTerminatorOpInterface.

@rriddle there is also another use of the ReturnLike trait in the scope of the DataFlowAnalysis. Currently, you check whether a terminator is ReturnLike. If not, you mark the following region successors to have reached a pessimistic fixpoint. This raises the question of whether we want to change this behavior to propagate lattice information in the context of "more return-like" operations.

Addressed reviewer comments and refined RegionBranchTerminatorOpInterface.
Adapted uses of hasTrait<ReturnLike> to use newly added functions (if possible).

Awesome work, thanks a lot :-)

In D100838#2743994, @herhut wrote:

In D100838#2741904, @tpopp wrote:

I've worked around this issue in my own code now, so what do you think about me just doing this rename? Then there will be no confusion between this pass and the new AliasAnalysis (and their definitions of aliasing). I think that confusion is good to avoid, and since I have a different solution for my own use case, I can avoid creating more confusion by creating another Analysis at this time.

+1 to renaming it to avoid confusion in the future.

I have to admit that my comment regarding all aliases of A was a bit misleading :-( At the time of writing, I accidentally had the "flow"-property (required by the BufferDeallocation phase) in mind. My comment was meant to address potentially "inconsistent" results of two "alias analyses" (of course, aliasing is a symmetric property!) :-)

I have to admit that I am not convinced by the general notion of a "dependency". In my opinion, BufferDependencyAnalysis::resolve(B) => {B, C, D}, does not give any guarantees about whether C and D actually depend on B in the sense of true "data dependencies". Instead, C and D can also be block arguments that are pure aliases without any read/write dependencies. Also, BufferAliasAnalysis::resolve(B) => {A, B, C, D} feels to me like A can be an alias of B, which is not actually the case, right? B has two aliases, namely C and D on the one hand. On the other hand, A has three aliases, namely B, C and D. Returning A as an alias of B could cause confusion in the future. What do you think about this?

@silvas @mehdi_amini @herhut based on the feedback and the discussion in the public Discourse forums, we will close this PR for now until there is a better solution to overcome these limitations in the future.

@silvas Our intention was not to "bypass anything", sorry for the confusion. As you have mentioned, the discussion went a bit "idle" and we had to more forwards to simplify the integration of the BufferDeallocation pass into other third-party sub projects. Therefore, we proposed this CL that realizes an extremely light-weight version of the Pass Interface being discussed in the forums. However, the proposed solution in the scope of this CL is meant to unblock others on the one hand and being minimally invasive on the other hand. In other words: as soon as we can come up with a better solution based on the Discourse discussion, we can easily "revert" or "update" this pass interface. Please note further that existing code will not break or require further updates after merging this CL.

Awesome work 🚀 I don't see any problems to land this CL after addressing the nits 🤓

Actually, it sounds like the direction we want to go with this is to split this functionality out. I'll do that in a separate patch.

Awesome work +1. I guess this should be ready to go after replacing some autos with their underlying types.

For example, FunctionLike doesn't guarantee that the op has a FunctionType, so all the code here where we modify the function type can't be written generically (see this thread for a similar issue:

Unfortunately, we cannot use this trait for the reasons you mentioned.

I guess this approach introduces a limitation with respect to applicability to arbitrary dialects. We are now able to match ReturnOp and CallOps only while the previous version supported a generic customization to arbitrary dialects, right?
I would recommend that we should try to match CallOpInterface and ReturnLike implementations to make this code more generic in favor of standard CallOp and ReturnOp-based matchers from the Std dialect.

The basic idea behind these generic type converts was to provide a highly customizable way to decompose and rewrite tuple types.
However, if there are no real users and as you are currently refactoring these parts into a separate pass anyway, it might be a good idea to simplify these conversion patterns.
See this CL for additional comments on the general refactoring process.

Addressed reviewer comments.

Refactored code and addressed reviewer comments.

Refined all parts of this PR and addressed all reviewer comments.

Addressed reviewer comments and changed the BufferAllocationHoisting pass to pay attention to escaping buffers via backedges.

Addressed reviewer comments regarding tests, comments and invariants.

Completed support for loops using structured control flow and addressed reviewer comments.

Addressed reviewer comments.

Added support for region-region control flow within operations that implement the RegionBranchOpInterface.
Added new test operations to verify more advanced region-region control-flow scenarios.

Refactored implementation and simplified the iteration over all successor regions.

Added extended support for the RegionOpInterface to query successor bindings for successor regions

Refactored access to getSuccessorOperands to distinguish between read-only and write-enabled accesses.

Added an additional comment and change to code to use the implicit OperandRange conversion operator.

Resolved merge conflicts and integrated an additional test case into an existing one in order to capture an additional special case.

Updated processing of aliases to avoid the aggressive insertion of copy operations in special cases.
Reformatted test cases.

Fixed corner cases in which no copies have been created due to aliasing (see reviewer comments).
Added additional test cases to simulate such special control-flow scenarios.
Changed behavior of the BufferPlacement pass to ignore Alloc operations with multiple allocation results.

Implemented a fix-point iteration to reduce the number of required copies.
Fixed minor issues (see review comments).

@mehdi_amini Thanks a lot for your feedback. Unfortunately, I haven't received some comments from him.